eolymp
bolt
Try our new interface for solving problems
Problems

Перегоны

Перегоны

Time limit 1 second
Memory limit 64 MiB

На некоторой железнодорожной ветке расположено N станций, которые последовательно пронумерованы числами от 1 до N. Известны расстояния между некоторыми станциями. Требуется точно вычислить длины всех перегонов между соседними станциями или указать, что это сделать невозможно (то есть приведенная информация является противоречивой или ее недостаточно).

Input data

Во входном файле записаны сначала числа N — количество станций (2N100) и E — количество пар станций, расстояния между которыми заданы (0E10000). Далее идет E троек чисел, первые два числа каждой тройки задают номера станций (это числа из диапазона от 1 до N), а третье — расстояние между этими станциями (все эти расстояния заданы точно и выражаются вещественными неотрицательными числами не более чем с 3-я знаками после десятичной точки).

Output data

В случае, когда восстановить длины перегонов можно однозначно, в выходной файл выведите сначала число 1, а затем N1 вещественное число. Первое из этих чисел должно соответствовать расстоянию от 1-й станции до 2-й, второе — от 2-й до 3-й, и так далее. Все числа должны быть выведены с точностью до 3-х знаков после десятичной точки.

Если приведенная информация о расстояниях между станциями является противоречивой или не позволяет однозначно точно восстановить длины перегонов, выведите в выходной файл одно число 2.

Examples

Input example #1
3 2
1 2 1.250
3 1 3
Output example #1
1
1.250 1.750