Najkraci

Ένα οδικό δίκτυο σε μια χώρα αποτελείται από ~N~ πόλεις και ~M~ μονόδρομους. Οι πόλεις αριθμούνται από ~1~ έως ~N~. Για κάθε δρόμο γνωρίζουμε τις πόλεις αφετηρίας και προορισμού, καθώς και το μήκος του.
Λέμε ότι ο δρόμος ~F~ είναι συνέχεια του δρόμου ~E~ εάν η πόλη προορισμού του δρόμου ~E~ είναι ίδια με την πόλη αφετηρίας του δρόμου ~F~. Ένα μονοπάτι από την πόλη ~A~ προς την πόλη ~B~ είναι μια ακολουθία δρόμου τέτοια που η αφετηρία του πρώτου δρόμου είναι η πόλη ~A~, κάθε άλλος δρόμος είναι η συνέχεια του προηγούμενου και ο προορισμός του τελευταίου δρόμου είναι η πόλη ~B~. Το μήκος του μονοπατιού είναι το άθροισμα των μηκών όλων των δρόμων σε αυτό.
Ένα μονοπάτι από το ~A~ στο ~B~ είναι το συντομότερο μονοπάτι εάν δεν υπάρχει άλλο μονοπάτι από το ~A~ στο ~B~ που να είναι μικρότερο σε μήκος.
Η δουλειά σας είναι να τυπώσετε, για κάθε δρόμο, πόσα διαφορετικά συντομότερα μονοπάτια που περιέχουν αυτόν τον δρόμο υπάρχουν, ως υπόλοιπο ακέραιας διαίρεσης (modulo) με το ~1\,000\,000\,007~.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~ και ~M (1 \le N \le 1\,500,\; 1 \le M \le 5\,000)~, τον αριθμό των πόλεων και δρόμων.
Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει τρεις θετικούς ακέραιους ~O~, ~D~ και ~L~. Αυτοί αντιπροσωπεύουν ένα μονόδρομο από την πόλη ~O~ προς την πόλη ~D~ μήκους ~L~. Οι αριθμοί ~O~ και ~D~ θα είναι διαφορετικοί και ο ~L~ θα είναι το πολύ ~10\,000~.

Έξοδος

Τυπώστε ~M~ ακέραιους αριθμούς τον καθένα στη δική του γραμμή – για κάθε δρόμο, τον αριθμό των διαφορετικών συντομότερων μονοπατιών που τον περιέχουν, ως υπόλοιπο ακέραιας διαίρεσης (modulo) με το ~1\,000\,000\,007~. Η σειρά αυτών των αριθμών πρέπει να ταιριάζει με τη σειρά των δρόμων στην είσοδο.

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~30%~ των πόντων, το ~N~ θα είναι το πολύ ~15~ και το ~M~ θα είναι το πολύ ~30~.
Στα αρχεία ελέγχου αξίας ~60%~ των πόντων, το ~N~ θα είναι το πολύ ~300~ και το ~M~ θα είναι το πολύ ~1\,000~.

Παραδείγματα

input

4 3
1 2 5
2 3 5
3 4 5

output

3
4
3

input

4 4
1 2 5
2 3 5
3 4 5
1 4 8

output

2
3
2
1

input

5 8
1 2 20
1 3 2
2 3 2
4 2 3
4 2 3
3 4 5
4 3 5
5 4 20

output

0
4
6
6
6
7
2
6