#pragma GCC optimize("O3") //#pragma GCC target("avx2") //#pragma GCC optimize("unroll-loops") #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef vector vi; typedef vector vll; typedef vector vld; typedef pair Pll; typedef pair Pin; ll INF = 1e16; int inf = 1e9; #define ALL(x) (x).begin(), (x).end() #define FOR(i, m, n) for (ll i = (m); i < (n); ++i) #define REVFOR(i, m, n) for (ll i = (n - 1); i >= (m); --i) #define REP(i, n) FOR(i, 0, n) #define REVREP(i, n) REVFOR(i, 0, n) #define fi first #define se second #define pb push_back #define mp make_pair #define eb emplace_back #define bcnt __builtin_popcountll #ifdef LOCAL #include #define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__); #else #define debug(...) 83; #endif void d_err() { cerr << endl; } template void d_err(H h, T... t) { cerr << h << " "; d_err(t...); } template void print(T x) { cout << x << "\n"; } template void print(vector& x) { int N = x.size(); REP(i, N) { if (i > 0) cout << " "; cout << x[i]; } cout << "\n"; } // UnionFind with potential template struct UnionFind { typedef function OP1; typedef function OP2; vector par; vector diff_weight; OP1 accum_op; OP1 diff_op; OP2 neg_op; UnionFind(int n, /// ↓ edit!!! OP1 accum_op=[](const T& a, const T& b) {return a + b;}, OP1 diff_op=[](const T& a, const T& b) {return a - b;}, OP2 neg_op=[](const T& a) {return -a;}, T unity=0 ): accum_op(accum_op), diff_op(diff_op), neg_op(neg_op) { init(n, unity); } void init(int n, T unity=0) { par.assign(n, -1); diff_weight.assign(n, unity); } int root(int x) { if (par[x] < 0) return x; int r = root(par[x]); diff_weight[x] = accum_op(diff_weight[x], diff_weight[par[x]]); return par[x] = r; } int issame(int x, int y) { return root(x) == root(y); } T weight(int x) { root(x); return diff_weight[x]; } // update with diff_op(weight(y), weight(x)) = w bool merge(int x, int y, T w = 0) { w = accum_op(w, weight(x)); w = diff_op(w, weight(y)); x = root(x); y = root(y); if (x == y) return false; // merge by size // force size of x to be bigger than that of y if (par[x] > par[y]) swap(x, y), w = neg_op(w); par[x] += par[y]; par[y] = x; diff_weight[y] = w; return true; } T diff(int x, int y) { return diff_op(weight(y), weight(x)); } ll size(int x) { return -par[root(x)]; } }; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); int n, m; cin >> n >> m; vector> dst(m); REP(i, m) { int s, t; ll d; cin >> s >> t >> d; dst[i] = make_pair(d, make_pair(s, t)); } sort(ALL(dst), greater<>()); UnionFind uf(n + 1); vector edge(n + 1); int i = 0; while(i < m) { ll w = dst[i].fi; while(i < m && dst[i].fi == w) { auto [s, t] = dst[i++].se; uf.merge(s, t); edge[s].eb(t); edge[t].eb(s); } if (uf.issame(1, n)) { vll dist(n + 1, INF); dist[1] = 0; queue> q; q.emplace(1, 0); while(q.size()) { auto [cur, d] = q.front(); q.pop(); ll d_nxt = d + 1; for(auto &e: edge[cur]) { if (dist[e] >= d_nxt) { dist[e] = d_nxt; q.emplace(e, d_nxt); } } } cout << w << " " << dist[n] << endl; return 0; } } }