The German University in Cairo (GUC) dorm houses are numbered from 1 to *n*. Underground water pipes connect these houses together. Each pipe has certain direction (water can flow only in this direction and not vice versa), and diameter (which characterizes the maximal amount of water it can handle).

For each house, there is at most one pipe going into it and at most one pipe going out of it. With the new semester starting, GUC student and dorm resident, Lulu, wants to install tanks and taps at the dorms. For every house with an outgoing water pipe and without an incoming water pipe, Lulu should install a water tank at that house. For every house with an incoming water pipe and without an outgoing water pipe, Lulu should install a water tap at that house. Each tank house will convey water to all houses that have a sequence of pipes from the tank to it. Accordingly, each tap house will receive water originating from some tank house.

In order to avoid pipes from bursting one week later (like what happened last semester), Lulu also has to consider the diameter of the pipes. The amount of water each tank conveys should not exceed the diameter of the pipes connecting a tank to its corresponding tap. Lulu wants to find the maximal amount of water that can be safely conveyed from each tank to its corresponding tap.
The first line contains two space-separated integers *n* and *p* (1 ≤ *n* ≤ 1000, 0 ≤ *p* ≤ *n*) — the number of houses and the number of pipes correspondingly. 

Then *p* lines follow — the description of *p* pipes. The *i*-th line contains three integers *a*<sub class="lower-index">*i*</sub> *b*<sub class="lower-index">*i*</sub> *d*<sub class="lower-index">*i*</sub>, indicating a pipe of diameter *d*<sub class="lower-index">*i*</sub> going from house *a*<sub class="lower-index">*i*</sub> to house *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>, 1 ≤ *d*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>).

It is guaranteed that for each house there is at most one pipe going into it and at most one pipe going out of it.
3 2
1 2 10
2 3 20
1
1 3 10
3 3
1 2 20
2 3 10
3 1 5
0
4 2
1 2 60
3 4 50
2
1 2 60
3 4 50
10 10
10 3 70
1 9 98
9 10 67
5 2 78
8 6 71
4 8 95
7 1 10
2 5 73
6 7 94
3 4 23
0
7 5
3 2 26
4 6 84
6 3 82
5 1 57
1 7 34
2
4 2 26
5 7 34
9 6
7 4 98
5 9 72
4 6 10
2 8 22
9 7 17
3 1 66
3
2 8 22
3 1 66
5 6 10
8 6
1 3 84
8 4 34
7 2 10
6 8 8
3 5 39
2 7 8
2
1 5 39
6 4 8
10 8
2 3 49
4 8 26
5 2 76
3 5 94
1 7 16
10 9 77
6 4 24
7 1 7
2
6 8 24
10 9 77
6 5
2 6 47
3 4 27
5 2 47
4 1 62
1 5 61
1
3 6 27
5 4
5 2 9
4 1 94
3 5 82
2 3 58
1
4 1 94
1000 0
0
2 2
1 2 1
2 1 1
0
44 42
4 37 166
34 25 47
28 19 367
20 14 811
8 3 878
39 1 925
35 9 206
32 18 841
16 44 503
5 20 426
22 34 896
44 43 471
17 33 577
40 22 317
24 31 818
37 11 292
21 39 888
6 8 983
43 36 170
11 21 662
36 17 942
18 7 356
2 32 220
12 5 774
19 27 193
13 40 63
15 10 510
30 35 869
41 24 736
42 4 180
23 41 261
9 28 501
29 15 983
10 30 638
7 13 402
26 12 754
25 6 597
27 29 57
1 16 933
31 42 135
33 38 718
14 23 361
2
2 3 47
26 38 135
35 33
22 7 978
5 6 566
20 10 198
6 17 170
7 27 627
24 19 659
31 30 130
34 8 365
23 12 716
4 29 217
8 20 156
26 35 142
3 2 419
15 1 448
17 24 91
18 33 962
30 22 822
9 16 847
2 9 470
10 25 981
16 31 359
19 28 283
28 34 199
11 5 660
25 23 176
29 18 235
12 14 765
14 11 81
27 21 61
21 13 651
35 3 583
1 32 767
13 4 256
2
15 32 448
26 33 61
33 28
12 15 574
11 13 714
13 33 62
9 28 391
22 19 235
6 20 655
23 9 25
8 29 994
21 30 133
17 18 170
32 7 470
14 21 418
7 31 431
3 1 185
1 14 538
33 12 250
31 22 694
2 27 945
16 26 584
19 32 317
27 2 904
15 25 748
29 3 754
24 4 287
18 10 775
30 11 401
10 8 653
28 5 70
5
6 20 655
16 26 584
17 25 62
23 5 25
24 4 287
3 1
1 2 10
1
1 2 10
1 0
0
2 0
0
3 0
0
n, p = map(int, input().split(' '))

is_vertex_source = [True for _ in range(n+1)]
vertex_edges = [None for _ in range(n+1)]
is_vertex_source[0] = None

for _ in range(p):
    a, b, diameter = map(int, input().split(' '))
    is_vertex_source[b] = False
    vertex_edges[a] = (b, diameter)

res = []

for j in range(n+1):
    if is_vertex_source[j]:
        next_vertex, maximal_flow = vertex_edges[j]
        while vertex_edges[next_vertex] is not None:
            next_vertex, current_flow = vertex_edges[next_vertex]
            maximal_flow = min(maximal_flow, current_flow)

        res.append((j, next_vertex, maximal_flow))

print(len(res))
for a, b, c in res:
    print(a, b, c)
