Беси собирается в путешествие по Cowland, которая имеет
\(N\) (\(2\le N\le 2\cdot 10^5\)) городов, пронумерованных от \(1\) до \(N\)
и \(M\) (\(1\le M\le 4\cdot 10^5\)) односторонних дорог.
\(i\)-ая дорога ведёт из города \(a_i\) в город \(b_i\) и имеет метку \(l_i\)
(\(1\le a_i,b_i\le N\), \(1\le l_i\le 10^9\)).
Путешествие длины \(k\) начинается в городе \(x_0\) - это
последовательность городов \(x_0, x_1, \ldots, x_k\), таких, что
что существует дорога из города \(x_i\) в город \(x_{i+1}\) для всех \(0\le i < k\).
Гарантируется, что не существует путешествий бесконечной длины, и что никакие две дороги
не соединяют одну и ту же пару городов.
Для каждого города Беси хочет узнать наидлиннейшее путешествие, начинающееся
в этом городе. Для некоторых стартовых городов может существовать несколько наидлиннейших
путешествий - из них Беси предпочитает путешествие с лексикографически минимальной
последовательностью меток дорог. Последовательность лексикографически меньше другой
последовательности такой же длины, если на первой позиции, где они различаются,
первая последовательность имеет меньший элемент, чем вторая последовательность.
Выведите длину и сумму меток дорог, предпочитаемого Беси путешествия, начинающегося из
каждого города.
ФОРМАТ ВВОДА (с клавиатуры):
Первая строка содержит
\(N\) и
\(M\).
Каждая из следующих \(M\) строк содержит три целых числа \(a_i\), \(b_i\), \(l_i\),
обозначающих дорогу из \(a_i\) в \(b_i\) с меткой \(l_i\).
ФОРМАТ ВЫВОДА (на экран):
Выведите
\(N\) строк.
\(i\)-ая строка должна содержать два разделённых одиночным пробелом
целых числа длину и сумму меток дорог предпочитаемого Бесси путешествия, начинающегося
в городе
\(i\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
4 3 10
4 2 10
3 1 10
2 1 10
4 1 10
|
0 0
1 10
1 10
2 20
|