Дана система из узлов и труб, по которым может течь вода. Для каждой трубы известна наибольшая скорость, с которой вода может протекать через нее. Известно, что вода течет по трубам таким образом, что за единицу времени в каждый узел (за исключением двух - источника и стока) втекает ровно столько воды, сколько из него вытекает. Более того, известно, что для любой пары узлов (включая источник и сток) сумма скоростей течения воды вдоль любого пути, их соединяющего, постоянна для данной пары узлов. Сумма берется таким образом, что если труба представлена в пути против направления движения воды в ней, то соответствующее слагаемое берется со знаком минус.

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

Трубы являются двусторонними, то есть вода в них может течь в любом направлении. Между любой парой узлов может быть более одной трубы.

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

В первой строке записано натуральное число N - количество узлов в системе (2 ≤ N ≤ 100). Известно, что источник имеет номер 1, а сток номер N. Во второй строке записано натуральное M (1 ≤ M ≤ 5000) - количество труб в системе. Далее в M строках идет описание труб. Каждая труба задается тройкой целых чисел Ai, Bi, Ci, где Ai, Bi - номера узлов, которые соединяет данная труба, а Ci (0 ≤ Ci ≤ 10000) - наибольшая допустимая скорость течения воды через данную трубу.

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

Выведите наибольшее количество воды, которое протекает между источником и стоком за единицу времени. Число выводите с точностью 10-3.