題目 2464:
信息學奧賽一本通T1558-聚會
時間限制: 2s
內(nèi)存限制: 192MB 提交: 11 解決: 5
題目描述
原題來自：AHOI 2008
Y 島風景美麗宜人，氣候溫和，物產(chǎn)豐富。Y 島上有 N 個城市，有 N?1 條城市間的道路連接著它們。每一條道路都連接某兩個城市。幸運的是，小可可通過這些道路可以走遍 Y 島的所有城市。神奇的是，乘車經(jīng)過每條道路所需要的費用都是一樣的。
小可可，小卡卡和小 YY 經(jīng)常想聚會，每次聚會，他們都會選擇一個城市，使得三個人到達這個城市的總費用最小。
由于他們計劃中還會有很多次聚會，每次都選擇一個地點是很煩人的事情，所以他們決定把這件事情交給你來完成。他們會提供給你地圖以及若干次聚會前他們所處的位置，希望你為他們的每一次聚會選擇一個合適的地點。
輸入格式
第一行兩個正整數(shù)，N 和 M。分別表示城市個數(shù)和聚會次數(shù)；
后面有 N?1 行，每行用兩個正整數(shù) A 和 B 表示編號為 A 和編號為 B 的城市之間有一條路。城市的編號是從 1 到 N 的；
再后面有 M 行，每行用三個正整數(shù)表示一次聚會的情況：小可可所在的城市編號，小卡卡所在的城市編號以及小 YY 所在的城市編號。
輸出格式
一共有 M 行，每行兩個數(shù) P 和 C，用一個空格隔開。表示第 i 次聚會的地點選擇在編號為 P 的城市，總共的費用是經(jīng)過 C 條道路所花費的費用。
樣例輸入
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
提示
數(shù)據(jù)范圍與提示：
40% 的數(shù)據(jù)中，1≤N,M≤2×103 ；
100% 的數(shù)據(jù)中，1≤N,M≤5×105。