http://codeforces.com/gym/100676/attachments
题目大意：
有n个城市，有m条路，每条路都有边长，如果某几个城市的路能组成一个环，那么在环中的这些城市就有传送门，能够瞬间抵达对方的城市（即距离为0），否则，就要走这条路，并且经过的路程为这条路的长度。
问，找一个城市作为这些城市的首都
要求：除了首都城市外，其他城市到首都的最大距离最短。
思路：
边双连通缩点以后就是一棵树，找树上的直径，首都一定是直径上的点。（orz，自己明明注意到了一定是直径上面的点，在之前的好多次的wa中却忘了是要找直径上的点了）
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
/*
思路：
双连通缩点，然后随便找一个点树dp，
树dp，距离最短的肯定就是直径上的某一个点
*/
const int maxn = 1e5 + ;
const int maxm = 2e5 + ;
const LL inf = 1e17;
vector<pair<int, LL> > G[maxn];
int n, m;
/*****************/
int dfstime, bcccnt;
bool iscut[maxn];
int bccnu[maxn], pre[maxn];
stack<int> s;
vector<int> bcc[maxn]; int dfs(int u, int fa){
int lowu = pre[u] = ++dfstime;
int len = G[u].size();
int child = ;
s.push(u);
for (int i = ; i < len; i++){
int v = G[u][i].fi;
if (pre[v] == -){
child++;
int lowv = dfs(v, u);
lowu = min(lowv, lowu);
if (lowv > pre[u]){
iscut[u] = true;
}
}
else if (pre[v] < pre[u] && v != fa){
lowu = min(lowu, pre[v]);
}
}
if (lowu == pre[u]){
bcccnt++;
while (true){///边双连通分量是不存在重点的
int v = s.top(); s.pop();
bccnu[v] = bcccnt;
bcc[bcccnt].pb(v);
if (v == u) break;
}
}
if (fa == - && child == ) iscut[u] = false;
return lowu;
} void get_connect(){
dfstime = bcccnt = ;
memset(iscut, false, sizeof(iscut));
memset(bccnu, , sizeof(bccnu));
memset(pre, -, sizeof(pre));
dfs(, -);
} vector<pair<int, LL> > new_edge[maxn];
void rebuild(){
///O(n + m)
for (int i = ; i <= bcccnt; i++){
for (int j = ; j < bcc[i].size(); j++){
int u = bcc[i][j];
for (int k = ; k < G[u].size(); k++){
int v = G[u][k].fi;
LL val = G[u][k].se;
if (bccnu[u] != bccnu[v]){
new_edge[bccnu[u]].push_back(mk(bccnu[v], val));
}
}
}
}
/* printf("bcccnt = %d\n", bcccnt); cout << "new_edge.output" << endl;
for (int i = 1; i <= bcccnt; i++){
for (int j = 0; j < new_edge[i].size(); j++){
printf("u = %d v = %d val = %d\n", i, new_edge[i][j].fi, new_edge[i][j].se);
}
cout << endl;
}
*/
} int p; LL maxval;
LL can[maxn];
void dfs1(int u, int fa, LL sum){
if (sum > maxval){
maxval = sum, p = u;
}
for (int i = ; i < new_edge[u].size(); i++){
int v = new_edge[u][i].fi;
LL tmp = new_edge[u][i].se;
if (v == fa) continue;
dfs1(v, u, sum + tmp);
}
} LL d1[maxn], d2[maxn];
///d1从最底下到目前节点的距离
///d2表示从根到目前节点的距离
void dfs2(int u, int fa, LL sum){
d2[u] = sum;
for (int i = ; i < new_edge[u].size(); i++){
int v = new_edge[u][i].fi;
LL val = new_edge[u][i].se;
if (v == fa) continue;
dfs2(v, u, sum + val);
d1[u] = max(d1[u], d1[v] + val);
}
} LL mini;
vector<int> ansp;
void dfs3(int u, int fa){
for (int i = ; i < new_edge[u].size(); i++){
int v = new_edge[u][i].fi;
LL val = new_edge[u][i].se;
if (v == fa) continue;
if (d1[u] - val == d1[v]){
dfs3(v, u);
LL tmp = max(d1[u], d2[u]);
if (mini > tmp){
ansp.clear(); mini = tmp; ansp.pb(u);
}
else if (mini == tmp){
ansp.pb(u);
}
}
}
} int main(){
int t; cin >> t;
while (t--){
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++){
G[i].clear(); bcc[i].clear();
new_edge[i].clear();
}
for (int i = ; i <= m; i++){
int u, v; LL val; scanf("%d%d%lld", &u, &v, &val);
G[u].pb(mk(v, val)); G[v].pb(mk(u, val));
}
get_connect();
rebuild();
p = , maxval = ;
dfs1(, -, ); memset(d1, , sizeof(d1));
memset(d2, , sizeof(d2));
ansp.clear();
dfs2(p, -, 0LL); mini = inf;
dfs3(p, -); int ans = n + ;
for (int i = ; i < ansp.size(); i++){
int u = ansp[i];
for (int j = ; j < bcc[u].size(); j++){
ans = min(ans, bcc[u][j]);
}
}
if (ans == n + ) {ans = , mini = ;}
printf("%d %lld\n", ans, mini);
}
return ;
}