// 標準入力を受け取るための準備 const fs = require('fs'); const input = fs.readFileSync('/dev/stdin', 'utf8').trim(); const lines = input.split('\n'); // --- TownConnectivity クラス (Union-Find) --- class TownConnectivity { // コンストラクタ (__init__ に相当) constructor(townNum) { // this は Python の self に相当 this.parent = new Array(townNum + 1).fill(-1); } // リーダーを見つける find メソッド find(townId) { if (this.parent[townId] < 0) { return townId; } else { // 経路圧縮 this.parent[townId] = this.find(this.parent[townId]); return this.parent[townId]; } } // 2つのグループを連結する union メソッド union(s, t) { let sRoot = this.find(s); let tRoot = this.find(t); if (sRoot === tRoot) { return; } // Union by Size if (this.parent[sRoot] > this.parent[tRoot]) { [sRoot, tRoot] = [tRoot, sRoot]; // swap } this.parent[sRoot] += this.parent[tRoot]; this.parent[tRoot] = sRoot; } // 連結しているか確認する isConnected メソッド isConnected(a, b) { return this.find(a) === this.find(b); } } // --- 各処理の関数 --- // findMax_wのJavaScriptバージョン function findMaxW_binarySearch(roads, townNum) { // ok: この体重なら絶対に到達できる保証がある値 let ok = 0; // ng: この体重では絶対に到達できない保証がある値 // roads[0][2]はソート後の最大耐久度 let ng = roads[0][2] + 1; // okとngの差が1になるまで繰り返す while (ng - ok > 1) { // 中央値を計算 const mid = Math.floor((ok + ng) / 2); // midの体重で到達可能か調べる const connectivity = new TownConnectivity(townNum); // 耐久度がmid以上の道でunionしていく for (const [s, t, w] of roads) { if (w >= mid) { connectivity.union(s, t); } else { // roadsはソート済みなので、これ以上見る必要はない break; } } // 都市1と終点が連結しているかチェック if (connectivity.isConnected(1, townNum)) { // 到達できる => midはOKな値。もっと上を目指す ok = mid; } else { // 到達できない => midはNGな値。もっと下を探す ng = mid; } } // ループ終了後、答えは必ず ok に入っている return ok; } // 隣接リストを作成する関数 function convertEdgeToAdjacency(roads, townNum, maxW) { const adList = new Array(townNum + 1).fill(0).map(() => new Set()); for (const [s, t, w] of roads) { if (w >= maxW) { adList[s].add(t); adList[t].add(s); } else { break; } } return adList; } // BFSで最短経路を見つける関数 function findShortestPath(townNum, adList, startNode, endNode) { // JSの配列をキューとして使う (pushで追加, shiftで取り出し) const queue = [startNode]; const distance = new Array(townNum + 1).fill(-1); distance[startNode] = 0; while (queue.length > 0) { const currentTown = queue.shift(); // 先頭から取り出す (popleft) if (currentTown === endNode) { return distance[endNode]; } for (const neighbor of adList[currentTown]) { if (distance[neighbor] === -1) { distance[neighbor] = distance[currentTown] + 1; queue.push(neighbor); // 末尾に追加 (append) } } } return -1; // 到達不能 } // --- メイン処理 --- function main() { // 最初の行から townNum と roadNum を読み取る const [townNum, roadNum] = lines[0].split(' ').map(Number); const roads = []; for (let i = 1; i <= roadNum; i++) { roads.push(lines[i].split(' ').map(Number)); } // wの降順にソート // (a, b) => b[2] - a[2] は Pythonの key=lambda x:x[2], reverse=True と同じ roads.sort((a, b) => b[2] - a[2]); const maxW = findMaxW_binarySearc(roads, townNum); const adList = convertEdgeToAdjacency(roads, townNum, maxW); const minPath = findShortestPath(townNum, adList, 1, townNum); console.log(maxW, minPath); } // スクリプトの実行 main();