A. Водоснабжение
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Корпуса общежития German University in Cairo (GUC) пронумерованы числами от 1 до n. Для обеспечения водоснабжения под землей корпуса соединены трубами. Все трубы — направленные, то есть вода может течь только в определенном направлении, и не может течь в обратном. Также для каждой трубы известен ее диаметр, он обозначает объем воды, который может выдержать эта труба. Для каждого корпуса имеется не более, чем одна входящая в него труба, и не более, чем одна исходящая из него труба.

С началом нового семестра, студент Лулу, проживающий в общежитии, хочет установить баки с запасами воды и краны для экстренного слива воды. Бак нужно установить в каждый корпус, который имеет выходящую из него трубу и не имеет входящей. Кран нужно установить во всех корпусах, где есть входящая труба, но нет выходящей. Таким образом получится, что вода из любого корпуса с баком сможет дойти до корпуса с краном.

Чтобы трубы не лопнули на вторую неделю, как это произошло в прошлом семестре, Лулу должен принять во внимание диаметр труб. Объем воды, которая протекает от корпуса с баком до корпуса с краном, не должен превосходить того, что могут выдержать трубы. Однако, выбрав пару корпусов, где будут установлены бак и кран, Лулу хочет, чтобы объем воды, протекающей между этими двумя корпусами, был максимально возможным.

Входные данные

В первой строке через пробел записано два целых числа n и p (1 ≤ n ≤ 1000, 0 ≤ p ≤ n) — количество корпусов и количество труб.

Затем следуют p строк — описание p труб, i-ая строка содержит три целых числа ai bi di. Она задает трубу диаметра di выходящую из корпуса ai и ведущую в корпус bi    (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ di ≤ 106).

Гарантируется, что для каждого корпуса имеется не более одной входящей трубы, и не более одной исходящей трубы.

Выходные данные

На первой строке выведите t — количество пар корпусов, где нужно установить бак и слив.

На следующих t строках выведите по три числа: tanki, tapi, и diameteri, где tanki ≠ tapi (1 ≤ i ≤ t). Здесь tanki и tapi — номера корпусов, где будут установлены бак и слив, соответственно, а diameteri — максимально возможный объем воды, который можно пропустить. Все эти t строк должны быть упорядочены в порядке возрастания tanki.

Примеры
Входные данные
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