// 標準入力を受け取るための準備 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); } } // --- 各処理の関数 --- // 最適化された方法で最大のwを見つける関数 function findMaxWOptimized(roads, townNum) { const connectivity = new TownConnectivity(townNum); for (const [s, t, w] of roads) { connectivity.union(s, t); if (connectivity.isConnected(1, townNum)) { return w; } } return 0; } // 隣接リストを作成する関数 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 = findMaxWOptimized(roads, townNum); const adList = convertEdgeToAdjacency(roads, townNum, maxW); const minPath = findShortestPath(townNum, adList, 1, townNum); console.log(maxW, minPath); } // スクリプトの実行 main();