#include #include using namespace std; using ll = long long; int main() { int N, M; cin >> N >> M; vector> E; vector U(M), V(M), W(M); for(int i = 0; i < M; i++) { cin >> U[i] >> V[i] >> W[i]; U[i]--, V[i]--; E.push_back({-W[i], U[i], V[i]}); } vector>> adj(N); sort(E.begin(), E.end()); vector seen(M); atcoder::dsu uf(N); int id = 0; int x = -1; for(const auto&[w, u, v] : E) { if(!uf.same(u, v)) { uf.merge(u, v); adj[u].push_back({v, -w}); adj[v].push_back({u, -w}); seen[id] = true; } if(uf.same(0, N - 1)) x = max(x, -w); id++; } for(int i = 0; i < M; i++) if(!seen[i] && x <= -E[i][0]) { adj[E[i][1]].push_back({E[i][2], -E[i][0]}); adj[E[i][2]].push_back({E[i][1], -E[i][0]}); } queue que; que.push(0); vector dist(N, -1); dist[0] = 0; while(!que.empty()) { int v = que.front(); que.pop(); for(const auto&[to, cst]: adj[v]) { if(dist[to] == -1) { dist[to] = dist[v] + 1; que.push(to); } } } cout << x << " " << dist[N - 1] << endl; }