#include #include using namespace std; using namespace atcoder; using ll=long long; using ld=long double; ld pie=3.14159265359; ll inf=80010010000000000; ll mod=1000000007; int main(){ ll n,m; cin >> n >> m; vector>>g(n); for (ll i = 0; i < m; i++) { ll s,t,d; cin >> s >> t >> d; s--,t--; g[s].push_back({t,d}); g[t].push_back({s,d}); } vectormemo(n,inf); memo[0]=0; queueque; vectormemo2(n,0); que.push(0); memo2[0]=inf; while (!que.empty()) { ll v=que.front(); que.pop(); for (ll i = 0; i < g[v].size(); i++) { if (memo2[g[v][i].first]memo[v]+1&&g[v][i].second>=memo2[n-1]) { memo[g[v][i].first]=memo[v]+1; que.push(g[v][i].first); } } } cout << memo2[n-1] << ' '<< memo[n-1] << endl; }