#region itumono using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Numerics; using System.Text; using System.Text.RegularExpressions; using static System.Math; using static Output; using static Consts; #region I/O public static class Output { public static void Put(string a) => Console.WriteLine(a); public static void Put(params object[] i) => Put(string.Join(" ", i)); public static void Put(IEnumerable a) => Put(string.Join(" ", a)); public static void PutV(IEnumerable a) { foreach (var z in a) Put(z); } public static void YN(bool i) { if (i) Put("Yes"); else Put("No"); } } public class Input { public static string Str => Console.ReadLine(); public static bool IsTypeEqual() => typeof(T).Equals(typeof(U)); public static T ConvertType(U a) => (T)Convert.ChangeType(a, typeof(T)); public static T Cast(string s) { if (IsTypeEqual()) return ConvertType(int.Parse(s)); else if (IsTypeEqual()) return ConvertType(long.Parse(s)); else if (IsTypeEqual()) return ConvertType(double.Parse(s)); else if (IsTypeEqual()) return ConvertType(char.Parse(s)); else if (IsTypeEqual()) return ConvertType(BigInteger.Parse(s)); else if (IsTypeEqual()) return ConvertType(decimal.Parse(s)); else return ConvertType(s); } public static T[] Castarr(string[] s) { var ret = new T[s.Length]; int i = 0; if (IsTypeEqual()) { var list = new List(); foreach (var t in s) { foreach (var u in t) { list.Add(ConvertType(char.Parse(u.ToString()))); } } return list.ToArray(); } foreach (var t in s) { if (IsTypeEqual()) ret[i++] = ConvertType(int.Parse(t)); else if (IsTypeEqual()) ret[i++] = ConvertType(long.Parse(t)); else if (IsTypeEqual()) ret[i++] = ConvertType(double.Parse(t)); else if (IsTypeEqual()) ret[i++] = ConvertType(BigInteger.Parse(t)); else ret[i++] = ConvertType(t); } return ret; } Queue q = new Queue(); void next() { var ss = Str.Split(' '); foreach (var item in ss) q.Enqueue(item); } public T cin() { if (!q.Any()) next(); return Cast(q.Dequeue()); } public T[] cinarr() { return Castarr(Str.Split(' ')); } public T[] cinarr(int n) { var ret = new T[n]; for (int i = 0; i < n; ++i) ret[i] = cin(); return ret; } public int Int => cin(); public long Long => cin(); public double Double => cin(); public char Char => cin(); public string String => cin(); public BigInteger BI => cin(); public int[] Intarr => cinarr(); public long[] Longarr => cinarr(); public double[] Doublearr => cinarr(); public char[] Chararr => cinarr(); public string[] Stringarr => cinarr(); public BigInteger[] BIarr => cinarr(); public void cin(out T t) { t = cin(); } public void mul(out T t, out U u) { t = cin(); u = cin(); } public void mul(out T t, out U u, out V v) { t = cin(); u = cin(); v = cin(); } public void mul(out T t, out U u, out V v, out W w) { t = cin(); u = cin(); v = cin(); w = cin(); } public void mul(out T t, out U u, out V v, out W w, out X x) { t = cin(); u = cin(); v = cin(); w = cin(); x = cin(); } public void mul(out T t, out U u, out V v, out W w, out X x, out Y y) { t = cin(); u = cin(); v = cin(); w = cin(); x = cin(); y = cin(); } public void mul(out T t, out U u, out V v, out W w, out X x, out Y y, out Z z) { t = cin(); u = cin(); v = cin(); w = cin(); x = cin(); y = cin(); z = cin(); } } #endregion class Program { static void Main(string[] args) { var CP = new CP(); CP.Solve(); } } #endregion itumono public static class Consts { public const int INF = 1 << 30; //public const long INF = 1L << 60; public const int MOD = 1000000007; //public const int MOD = 998244353; } public class CP { Input cin = new Input(); public void Solve() { var n = cin.Int; var m = cin.Int; var edge = Enumerable.Range(0, n).Select(_ => new List<(int to, int d)>()).ToArray(); for (int i = 0; i < m; ++i) { var s = cin.Int - 1; var t = cin.Int - 1; var d = cin.Int; edge[s].Add((t, d)); edge[t].Add((s, d)); } int ok = 0; int ng = INF; while (ng - ok > 1) { var cur = (ok + ng) / 2; if (dijkstra(0, edge, cur)[n - 1] != INF) ok = cur; else ng = cur; } Put(ok, dijkstra(0, edge, ok)[n - 1]); } public int[] dijkstra(int from, List<(int to, int d)>[] edge, int max) { var ret = Enumerable.Repeat(INF, edge.Length).ToArray(); ret[from] = 0; var pq = new PriorityQueue<(int v, int d)>((a, b) => b.d - a.d); pq.Enqueue((from, 0)); while (pq.Any()) { var q = pq.Dequeue(); foreach (var next in edge[q.v]) { if (next.d < max) continue; if (ret[next.to] > q.d + 1) { ret[next.to] = q.d + 1; pq.Enqueue((next.to, ret[next.to])); } } } return ret; } } public class PriorityQueue { List _item; public int Count { get { return _item.Count; } } bool _isascend { get; set; } public T Peek { get { return _item[0]; } } Comparison Comp; public PriorityQueue(bool IsAscend = true, IEnumerable list = null) : this(Comparer.Default.Compare, IsAscend, list) { } public PriorityQueue(Comparison cmp, bool IsAscend = true, IEnumerable list = null) { _item = new List(); _isascend = IsAscend; this.Comp = cmp; if (list != null) { _item.AddRange(list); Build(); } } private int Compare(int i, int j) => (_isascend ? -1 : 1) * Comp(_item[i], _item[j]); private void Swap(int i, int j) { var t = _item[i]; _item[i] = _item[j]; _item[j] = t; } private int Parent(int i) => (i - 1) >> 1; private int Left(int i) => (i << 1) + 1; public T Enqueue(T val) { int i = _item.Count; _item.Add(val); while (i > 0) { int p = Parent(i); if (Compare(i, p) > 0) Swap(i, p); i = p; } return val; } private void Heapify(int index) { for (int i = index, j; (j = Left(i)) < _item.Count; i = j) { if (j != _item.Count - 1 && Compare(j, j + 1) < 0) j++; if (Compare(i, j) < 0) Swap(i, j); } } public T Dequeue() { T val = _item[0]; _item[0] = _item[_item.Count - 1]; _item.RemoveAt(_item.Count - 1); Heapify(0); return val; } private void Build() { for (var i = (_item.Count >> 1) - 1; i >= 0; i--) Heapify(i); } public bool Any() => Count > 0; }