Дорожная сеть города  представляет собой N перекрёстков, соединённых M дорогами с двусторонним движением.

Стартовый перекрёсток (начало маршрута) - 1, финальный перекрёсток - N.

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

Первая строка содержит два целых числа N и M — количество перекрёстков в городе  и количество дорог соответственно (2 ≤ N ≤  1000, 1 ≤ M ≤ 2⋅10^5).

Каждая из следующих M строк содержит три целых числа ai, bi и ci (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ ci ≤ 1000) — номера перекрёстков, соединяемых i-й дорогой, и длину этой дороги.

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

Ввод
3 3
1 2 1
1 3 2
2 3 1

Вывод
2 2

Проверочные: https://drive.google.com/file/d/0B-W6XTyb1bPuWi0xamNEZzVnUDA/view?usp=sharing

Контрольные: https://drive.google.com/file/d/0B-W6XTyb1bPuZW94MEdQRWlPQzg/view?usp=sharing