// 想定TLE (嘘 Dijkstra,昇順) #include #include #include #include #include using namespace std; #include int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector> edges; for (int e = 0; e < M; e++) { int s, t, d; cin >> s >> t >> d; edges.emplace_back(d, s - 1, t - 1); } sort(edges.rbegin(), edges.rend()); atcoder::dsu uf(N); int ret = 1 << 30; for (auto [d, s, t] : edges) { if (!uf.same(0, N - 1)) ret = min(ret, d); uf.merge(s, t); } vector> to(N); for (auto [w, s, t] : edges) { if (w >= ret) to[s].push_back(t), to[t].push_back(s); } vector dist(N, 1 << 30); dist[0] = 0; priority_queue> q; q.emplace(0, 0); while (!q.empty()) { const auto [dnow, now] = q.top(); q.pop(); if (dist[now] < dnow) continue; for (auto nxt : to[now]) { if (dist[nxt] > dist[now] + 1) { dist[nxt] = dist[now] + 1; q.emplace(dist[nxt], nxt); } } } cout << ret << ' ' << dist.back() << '\n'; }