#include<bits/stdc++.h>
using namespace std;
#define sz 100100
#define MOD 1000000007
#define ll long long
vector<pair<int, int>>adj[sz];
int minedges[sz];
int maxedges[sz];
ll dist[sz];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
while (m--)
{
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>pq;
for (ll i = 1; i <= n; i++)
dist[i] = 1e16;
minedges[1] = maxedges[1] = 0;
pq.push({0, 1});
ll cnt = 0;
while (!pq.empty())
{
pair<ll, int>cur = pq.top();
pq.pop();
if (cur.first > dist[cur.second])
continue;
for (auto it : adj[cur.second])
{
if (it.second + cur.first == dist[it.first])
{
minedges[it.first] = min(minedges[it.first], minedges[cur.second] + 1);
maxedges[it.first] = max(maxedges[it.first], maxedges[cur.second] + 1);
pq.push({cur.first + it.second, it.first});
if (it.first == n)
cnt = cnt + 1;
}
else if (it.second + cur.first < dist[it.first])
{
minedges[it.first] = minedges[cur.second] + 1;
maxedges[it.first] = maxedges[cur.second] + 1;
dist[it.first] = it.second + cur.first;
pq.push({cur.first + it.second, it.first});
if (it.first == n)
cnt = 1;
}
}
}
cout << dist[n] << " " << cnt << " " << minedges[n] << " " << maxedges[n];
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBzeiAxMDAxMDAKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwojZGVmaW5lIGxsIGxvbmcgbG9uZwp2ZWN0b3I8cGFpcjxpbnQsIGludD4+YWRqW3N6XTsKaW50IG1pbmVkZ2VzW3N6XTsKaW50IG1heGVkZ2VzW3N6XTsKbGwgZGlzdFtzel07CmludCBtYWluKCkKewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKDApOyBjb3V0LnRpZSgwKTsKCWludCBuLCBtOyBjaW4gPj4gbiA+PiBtOwoJd2hpbGUgKG0tLSkKCXsKCQlpbnQgYSwgYiwgYzsgY2luID4+IGEgPj4gYiA+PiBjOwoJCWFkalthXS5wdXNoX2JhY2soe2IsIGN9KTsKCX0KCXByaW9yaXR5X3F1ZXVlPHBhaXI8bGwsIGludD4sIHZlY3RvcjxwYWlyPGxsLCBpbnQ+PiwgZ3JlYXRlcjxwYWlyPGxsLCBpbnQ+Pj5wcTsKCWZvciAobGwgaSA9IDE7IGkgPD0gbjsgaSsrKQoJCWRpc3RbaV0gPSAxZTE2OwoJbWluZWRnZXNbMV0gPSBtYXhlZGdlc1sxXSA9IDA7CglwcS5wdXNoKHswLCAxfSk7CglsbCBjbnQgPSAwOwoJd2hpbGUgKCFwcS5lbXB0eSgpKQoJewoJCXBhaXI8bGwsIGludD5jdXIgPSBwcS50b3AoKTsKCQlwcS5wb3AoKTsKCQlpZiAoY3VyLmZpcnN0ID4gZGlzdFtjdXIuc2Vjb25kXSkKCQkJY29udGludWU7CgkJZm9yIChhdXRvIGl0IDogYWRqW2N1ci5zZWNvbmRdKQoJCXsKCQkJaWYgKGl0LnNlY29uZCArIGN1ci5maXJzdCA9PSBkaXN0W2l0LmZpcnN0XSkKCQkJewoJCQkJbWluZWRnZXNbaXQuZmlyc3RdID0gbWluKG1pbmVkZ2VzW2l0LmZpcnN0XSwgbWluZWRnZXNbY3VyLnNlY29uZF0gKyAxKTsKCQkJCW1heGVkZ2VzW2l0LmZpcnN0XSA9IG1heChtYXhlZGdlc1tpdC5maXJzdF0sIG1heGVkZ2VzW2N1ci5zZWNvbmRdICsgMSk7CgkJCQlwcS5wdXNoKHtjdXIuZmlyc3QgKyBpdC5zZWNvbmQsIGl0LmZpcnN0fSk7CgkJCQlpZiAoaXQuZmlyc3QgPT0gbikKCQkJCQljbnQgPSBjbnQgKyAxOwoJCQl9CgkJCWVsc2UgaWYgKGl0LnNlY29uZCArIGN1ci5maXJzdCA8IGRpc3RbaXQuZmlyc3RdKQoJCQl7CgkJCQltaW5lZGdlc1tpdC5maXJzdF0gPSBtaW5lZGdlc1tjdXIuc2Vjb25kXSArIDE7CgkJCQltYXhlZGdlc1tpdC5maXJzdF0gPSBtYXhlZGdlc1tjdXIuc2Vjb25kXSArIDE7CgkJCQlkaXN0W2l0LmZpcnN0XSA9IGl0LnNlY29uZCArIGN1ci5maXJzdDsKCQkJCXBxLnB1c2goe2N1ci5maXJzdCArIGl0LnNlY29uZCwgaXQuZmlyc3R9KTsKCQkJCWlmIChpdC5maXJzdCA9PSBuKQoJCQkJCWNudCA9IDE7CgkJCX0KCQl9Cgl9Cgljb3V0IDw8IGRpc3Rbbl0gPDwgIiAiIDw8IGNudCA8PCAiICIgPDwgbWluZWRnZXNbbl0gPDwgIiAiIDw8IG1heGVkZ2VzW25dOwoJcmV0dXJuIDA7Cn0=