C. Транспортный поток в Берляндии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Транспортный поток в Берляндии — совсем не такой как в других странах. Столица Берляндии состоит из n перекрестков и m дорог. Каждая дорога соединяет пару перекрестков. Между парой перекрестков может быть несколько дорог. Для каждой дороги известна пропускная способность: величина ci — максимальное количество машин, которое может проехать по дороге в любом направлении в единицу времени. Для каждой дороги машины могут двигаться по ней в одном из двух направлений, то есть двигаться как в одном, так и другом направлении одновременно машины не могут. Транспортным потоком для дороги называется количество машин, которое проезжает через нее за единицу времени. Для дороги (ai, bi) эта величина отрицательна, если движение транспорта происходит от bi к ai. Поток для дороги может быть нецелым числом.

В столице есть два особых перекрестка — въезд в город (перекресток 1) и выезд из города (перекресток n). Для всех остальных перекрестков верно, что поток в них никуда не теряется. То есть для всех перекрестков кроме 1 и n сумма потока входящего в перекресток равна сумме исходящего потока.

Необычная особенность дорожного потока в столице Берляндии — для любой пары перекрестков (x, y) сумма потоков вдоль любого пути из x в y не меняется от выбора пути. В такую сумму входят потоки по всем дорогам на пути (возможно со знаком «минус», если движение по дороге направлено против движения по дороге в пути от x в y).

Ваша задача — найти наибольший поток, который может проходить через город за единицу времени, а также соответствующий поток для каждой дороги.

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

В первой строке записано натуральное число n — количество перекрестков (2 ≤ n ≤ 100). Во второй строке записано целое число m (1 ≤ m ≤ 5000) — количество дорог. Далее в m строках идут описания дорог. Каждая дорога задается тройкой целых чисел ai, bi, ci, где ai, bi — номера перекрестков, которые соединяет данная дорога, а ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ ci ≤ 10000) — наибольший допустимый поток через данную дорогу.

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

В первую строку выведите искомый наибольший поток через город. Далее выведите m строк, в каждой из которых выведите поток по соответствующей дороге. Если направление не совпадает с порядком перекрестков, заданным во входных данных, то выводите поток со знаком минус. Числа выводите с точностью не менее пяти знаков после десятичной точки.

Если оптимальных потоков несколько, выведите любой из них.

Примеры
Входные данные
2
3
1 2 2
1 2 4
2 1 1000
Выходные данные
6.00000
2.00000
2.00000
-2.00000
Входные данные
7
11
1 2 7
1 2 7
1 3 7
1 4 7
2 3 7
2 5 7
3 6 7
4 7 7
5 4 7
5 6 7
6 7 7
Выходные данные
13.00000
2.00000
2.00000
3.00000
6.00000
1.00000
3.00000
4.00000
7.00000
1.00000
2.00000
6.00000