Ви збираєтеся подорожувати з A до B на літаку. Ви б хотіли отримати відповіді на питання:

• яка мінімальна ціна такого маршруту?
• скільки існує мінімальних маршрутів? (по модулю \(10^9+7\))
• яка мінімальна кількість рейсів на маршруті за мінімальною ціною?
• яка максимальна кількість рейсів на маршруті з мінімальною ціною?

Обмеження

• \(1≤n≤10^5\)
• \(1≤m≤2⋅10^5\)
• \(1≤ a,b≤n\)
• \(1≤c≤10^9\)

Формат вхідних даних

У першому рядку вхідних даних записано два цілі числа \(n\) і \(m\): кількість міст і кількість рейсів. Міста пронумеровані цифрами \(1,2,…,n\). Місто 1 – A, а місто \(n\) – B.

Після цього йдуть \(m\) рядків, що описують польоти. У кожному рядку є три цілі числа \(a\), \(b\) і \(c\): є рейс з міста \(a\) до міста \(b\) з ціною \(c\).

Усі рейси здійснюються в один бік. Ви можете припустити, що є маршрут із A до B.

Формат вихідних даних

Вивести чотири цілі числа відповідно до постановки задачі.

Приклад вхідних даних

4 5
1 4 5
1 2 4
2 4 5
1 3 2
3 4 3

Приклад вихідних даних

5 2 1 2