#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define out(a) copy(a.begin(),a.end(),ostream_iterator<int>(cout," "))
#define pr pair<int,int>
#define pp(a,b,c) make_pair(make_pair(a,b),c)
const int N = 1e5 + 100;
int t, n, m, low[N], disc[N], _par[N], par[N], vist[N], id;
ll best, l[N], r[N];
int src, des;
vector<vector<pair<int, int> > > arr;
vector<pair<pr,int> >edges,bridges;
bool cmp(pair<pr,int>a,pair<pr,int>b) {
if(a.first.first != b.first.first)
return a.first.first < b.first.first;
return a.first.second < b.first.second;
}
void dfs(int x) {
static int tim = 0;
low[x] = disc[x] = ++tim;
for (int i = 0, ln = arr[x].size(); i < ln; ++i) {
int y = arr[x][i].first, z = arr[x][i].second;
if (disc[y] == -1) {
par[y] = x;
dfs(y);
low[x] = min(low[x], low[y]);
if (low[y] > disc[x]) {
pair<pr,int>tmp = pp(min(x,y),max(x,y),z);
bridges.push_back(tmp);
}
} else if (par[x] != y)
low[x] = min(low[x], disc[y]);
}
}
void dfs(int x, ll dist) {
if (dist >= best) {
if (dist == best)
des = min(des, x);
else
des = x;
best = dist;
}
vist[x] = id;
for (int i = 0, ln = arr[x].size(); i < ln; ++i) {
int y = arr[x][i].first, z = arr[x][i].second;
if (vist[y] == id)
continue;
par[y] = x;
dfs(y, dist + (ll) z);
}
}
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
void unite(int x, int y) {
int a = find(x), b = find(y);
if (a > b)
swap(a, b);
par[b] = a;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
arr.clear();
arr.resize(n + 1);
edges.clear();
bridges.clear();
while (m--) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
if (x > y)
swap(x, y);
--x,--y;
arr[x].push_back(make_pair(y, z));
arr[y].push_back(make_pair(x, z));
disc[x] = disc[y] = par[x] = par[y] = -1;
edges.push_back(pp(x, y, z));
}
dfs(0);
sort(bridges.begin(), bridges.end());
for (int i = 0; i <= n; ++i)
par[i] = i;
for (size_t i = 0; i < edges.size(); ++i) {
int x = edges[i].first.first, y = edges[i].first.second;
if (binary_search(bridges.begin(), bridges.end(), pp(x, y, 0), cmp))
continue;
unite(x, y);
}
edges.clear();
arr.clear();
arr.resize(n + 1);
for (size_t i = 0; i < bridges.size(); ++i) {
int x = bridges[i].first.first, y = bridges[i].first.second;
int a = find(x), b = find(y);
arr[a].push_back(make_pair(b, bridges[i].second));
arr[b].push_back(make_pair(a, bridges[i].second));
edges.push_back(pp(a, b, bridges[i].second));
}
sort(edges.begin(), edges.end());
src = find(0);
id++;
best = 0;
dfs(src, 0);
memset(par, -1, sizeof par);
memset(_par, -1, sizeof _par);
src = des;
best = 0;
++id;
dfs(src, 0);
int x = des;
ll sum = 0;
int ans = -1;
while (par[x] != -1) {
int p = x;
x = par[x];
_par[x] = p;
pair<pr,int>tmp = pp(min(x,p),max(x,p),0);
int pos = lower_bound(edges.begin(), edges.end(), tmp, cmp)
- edges.begin();
sum += edges[pos].second;
l[x] = sum;
}
sum = 0;
while (_par[x] != -1) {
int p = x;
x = _par[x];
pair<pr,int>tmp = pp(min(x,p),max(x,p),0);
int pos = lower_bound(edges.begin(), edges.end(), tmp, cmp)
- edges.begin();
sum += edges[pos].second;
r[x] = sum;
}
sum = LLONG_MAX;
while (x != -1) {
ll diff = max(l[x], r[x]);
if (sum >= diff) {
if (sum == diff)
ans = min(ans, x);
else
ans = x;
sum = diff;
}
x = par[x];
}
printf("%d %lld\n", ans+1, sum);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgb3V0KGEpIGNvcHkoYS5iZWdpbigpLGEuZW5kKCksb3N0cmVhbV9pdGVyYXRvcjxpbnQ+KGNvdXQsIiAiKSkKI2RlZmluZSBwciBwYWlyPGludCxpbnQ+CiNkZWZpbmUgcHAoYSxiLGMpIG1ha2VfcGFpcihtYWtlX3BhaXIoYSxiKSxjKQpjb25zdCBpbnQgTiA9IDFlNSArIDEwMDsKaW50IHQsIG4sIG0sIGxvd1tOXSwgZGlzY1tOXSwgX3BhcltOXSwgcGFyW05dLCB2aXN0W05dLCBpZDsKbGwgYmVzdCwgbFtOXSwgcltOXTsKaW50IHNyYywgZGVzOwoKdmVjdG9yPHZlY3RvcjxwYWlyPGludCwgaW50PiA+ID4gYXJyOwp2ZWN0b3I8cGFpcjxwcixpbnQ+ID5lZGdlcyxicmlkZ2VzOwpib29sIGNtcChwYWlyPHByLGludD5hLHBhaXI8cHIsaW50PmIpIHsKICAgIGlmKGEuZmlyc3QuZmlyc3QgIT0gYi5maXJzdC5maXJzdCkKICAgIHJldHVybiBhLmZpcnN0LmZpcnN0IDwgYi5maXJzdC5maXJzdDsKICAgIHJldHVybiBhLmZpcnN0LnNlY29uZCA8IGIuZmlyc3Quc2Vjb25kOwp9CnZvaWQgZGZzKGludCB4KSB7CiAgICBzdGF0aWMgaW50IHRpbSA9IDA7CiAgICBsb3dbeF0gPSBkaXNjW3hdID0gKyt0aW07CiAgICBmb3IgKGludCBpID0gMCwgbG4gPSBhcnJbeF0uc2l6ZSgpOyBpIDwgbG47ICsraSkgewogICAgICAgIGludCB5ID0gYXJyW3hdW2ldLmZpcnN0LCB6ID0gYXJyW3hdW2ldLnNlY29uZDsKICAgICAgICBpZiAoZGlzY1t5XSA9PSAtMSkgewogICAgICAgICAgICBwYXJbeV0gPSB4OwogICAgICAgICAgICBkZnMoeSk7CiAgICAgICAgICAgIGxvd1t4XSA9IG1pbihsb3dbeF0sIGxvd1t5XSk7CiAgICAgICAgICAgIGlmIChsb3dbeV0gPiBkaXNjW3hdKSB7CiAgICAgICAgICAgICAgICBwYWlyPHByLGludD50bXAgPSBwcChtaW4oeCx5KSxtYXgoeCx5KSx6KTsKICAgICAgICAgICAgICAgIGJyaWRnZXMucHVzaF9iYWNrKHRtcCk7CiAgICAgICAgICAgIH0KICAgICAgICB9IGVsc2UgaWYgKHBhclt4XSAhPSB5KQogICAgICAgIGxvd1t4XSA9IG1pbihsb3dbeF0sIGRpc2NbeV0pOwogICAgfQp9CnZvaWQgZGZzKGludCB4LCBsbCBkaXN0KSB7CiAgICBpZiAoZGlzdCA+PSBiZXN0KSB7CiAgICAgICAgaWYgKGRpc3QgPT0gYmVzdCkKICAgICAgICAgICAgZGVzID0gbWluKGRlcywgeCk7CiAgICAgICAgZWxzZQogICAgICAgICAgICBkZXMgPSB4OwogICAgICAgIGJlc3QgPSBkaXN0OwogICAgfQogICAgdmlzdFt4XSA9IGlkOwogICAgZm9yIChpbnQgaSA9IDAsIGxuID0gYXJyW3hdLnNpemUoKTsgaSA8IGxuOyArK2kpIHsKICAgICAgICBpbnQgeSA9IGFyclt4XVtpXS5maXJzdCwgeiA9IGFyclt4XVtpXS5zZWNvbmQ7CiAgICAgICAgaWYgKHZpc3RbeV0gPT0gaWQpCiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIHBhclt5XSA9IHg7CiAgICAgICAgZGZzKHksIGRpc3QgKyAobGwpIHopOwogICAgfQp9CmludCBmaW5kKGludCB4KSB7CiAgICByZXR1cm4gcGFyW3hdID09IHggPyB4IDogcGFyW3hdID0gZmluZChwYXJbeF0pOwp9CnZvaWQgdW5pdGUoaW50IHgsIGludCB5KSB7CiAgICBpbnQgYSA9IGZpbmQoeCksIGIgPSBmaW5kKHkpOwogICAgaWYgKGEgPiBiKQogICAgICAgIHN3YXAoYSwgYik7CiAgICBwYXJbYl0gPSBhOwp9CmludCBtYWluKCkgewojaWZuZGVmIE9OTElORV9KVURHRQogICAgZnJlb3BlbigiYS5pbiIsICJyIiwgc3RkaW4pOwojZW5kaWYKICAgIHNjYW5mKCIlZCIsICZ0KTsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBzY2FuZigiJWQgJWQiLCAmbiwgJm0pOwogICAgICAgIGFyci5jbGVhcigpOwogICAgICAgIGFyci5yZXNpemUobiArIDEpOwogICAgICAgIGVkZ2VzLmNsZWFyKCk7CiAgICAgICAgYnJpZGdlcy5jbGVhcigpOwogICAgICAgIHdoaWxlIChtLS0pIHsKICAgICAgICAgICAgaW50IHgsIHksIHo7CiAgICAgICAgICAgIHNjYW5mKCIlZCAlZCAlZCIsICZ4LCAmeSwgJnopOwogICAgICAgICAgICBpZiAoeCA+IHkpCiAgICAgICAgICAgICAgICBzd2FwKHgsIHkpOwogICAgICAgICAgICAtLXgsLS15OwogICAgICAgICAgICBhcnJbeF0ucHVzaF9iYWNrKG1ha2VfcGFpcih5LCB6KSk7CiAgICAgICAgICAgIGFyclt5XS5wdXNoX2JhY2sobWFrZV9wYWlyKHgsIHopKTsKICAgICAgICAgICAgZGlzY1t4XSA9IGRpc2NbeV0gPSBwYXJbeF0gPSBwYXJbeV0gPSAtMTsKICAgICAgICAgICAgZWRnZXMucHVzaF9iYWNrKHBwKHgsIHksIHopKTsKICAgICAgICB9CiAgICAgICAgZGZzKDApOwogICAgICAgIHNvcnQoYnJpZGdlcy5iZWdpbigpLCBicmlkZ2VzLmVuZCgpKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8PSBuOyArK2kpCiAgICAgICAgICAgIHBhcltpXSA9IGk7CiAgICAgICAgZm9yIChzaXplX3QgaSA9IDA7IGkgPCBlZGdlcy5zaXplKCk7ICsraSkgewogICAgICAgICAgICBpbnQgeCA9IGVkZ2VzW2ldLmZpcnN0LmZpcnN0LCB5ID0gZWRnZXNbaV0uZmlyc3Quc2Vjb25kOwogICAgICAgICAgICBpZiAoYmluYXJ5X3NlYXJjaChicmlkZ2VzLmJlZ2luKCksIGJyaWRnZXMuZW5kKCksIHBwKHgsIHksIDApLCBjbXApKQogICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgIHVuaXRlKHgsIHkpOwogICAgICAgIH0KICAgICAgICBlZGdlcy5jbGVhcigpOwogICAgICAgIGFyci5jbGVhcigpOwogICAgICAgIGFyci5yZXNpemUobiArIDEpOwogICAgICAgIGZvciAoc2l6ZV90IGkgPSAwOyBpIDwgYnJpZGdlcy5zaXplKCk7ICsraSkgewogICAgICAgICAgICBpbnQgeCA9IGJyaWRnZXNbaV0uZmlyc3QuZmlyc3QsIHkgPSBicmlkZ2VzW2ldLmZpcnN0LnNlY29uZDsKICAgICAgICAgICAgaW50IGEgPSBmaW5kKHgpLCBiID0gZmluZCh5KTsKICAgICAgICAgICAgYXJyW2FdLnB1c2hfYmFjayhtYWtlX3BhaXIoYiwgYnJpZGdlc1tpXS5zZWNvbmQpKTsKICAgICAgICAgICAgYXJyW2JdLnB1c2hfYmFjayhtYWtlX3BhaXIoYSwgYnJpZGdlc1tpXS5zZWNvbmQpKTsKICAgICAgICAgICAgZWRnZXMucHVzaF9iYWNrKHBwKGEsIGIsIGJyaWRnZXNbaV0uc2Vjb25kKSk7CiAgICAgICAgfQogICAgICAgIHNvcnQoZWRnZXMuYmVnaW4oKSwgZWRnZXMuZW5kKCkpOwogICAgICAgIHNyYyA9IGZpbmQoMCk7CiAgICAgICAgaWQrKzsKICAgICAgICBiZXN0ID0gMDsKICAgICAgICBkZnMoc3JjLCAwKTsKICAgICAgICBtZW1zZXQocGFyLCAtMSwgc2l6ZW9mIHBhcik7CiAgICAgICAgbWVtc2V0KF9wYXIsIC0xLCBzaXplb2YgX3Bhcik7CiAgICAgICAgc3JjID0gZGVzOwogICAgICAgIGJlc3QgPSAwOwogICAgICAgICsraWQ7CiAgICAgICAgZGZzKHNyYywgMCk7CiAgICAgICAgaW50IHggPSBkZXM7CiAgICAgICAgbGwgc3VtID0gMDsKICAgICAgICBpbnQgYW5zID0gLTE7CiAgICAgICAgd2hpbGUgKHBhclt4XSAhPSAtMSkgewogICAgICAgICAgICBpbnQgcCA9IHg7CiAgICAgICAgICAgIHggPSBwYXJbeF07CiAgICAgICAgICAgIF9wYXJbeF0gPSBwOwogICAgICAgICAgICBwYWlyPHByLGludD50bXAgPSBwcChtaW4oeCxwKSxtYXgoeCxwKSwwKTsKICAgICAgICAgICAgaW50IHBvcyA9IGxvd2VyX2JvdW5kKGVkZ2VzLmJlZ2luKCksIGVkZ2VzLmVuZCgpLCB0bXAsIGNtcCkKICAgICAgICAgICAgICAgICAgICAtIGVkZ2VzLmJlZ2luKCk7CiAgICAgICAgICAgIHN1bSArPSBlZGdlc1twb3NdLnNlY29uZDsKICAgICAgICAgICAgbFt4XSA9IHN1bTsKICAgICAgICB9CiAgICAgICAgc3VtID0gMDsKICAgICAgICB3aGlsZSAoX3Bhclt4XSAhPSAtMSkgewogICAgICAgICAgICBpbnQgcCA9IHg7CiAgICAgICAgICAgIHggPSBfcGFyW3hdOwogICAgICAgICAgICBwYWlyPHByLGludD50bXAgPSBwcChtaW4oeCxwKSxtYXgoeCxwKSwwKTsKICAgICAgICAgICAgaW50IHBvcyA9IGxvd2VyX2JvdW5kKGVkZ2VzLmJlZ2luKCksIGVkZ2VzLmVuZCgpLCB0bXAsIGNtcCkKICAgICAgICAgICAgICAgICAgICAtIGVkZ2VzLmJlZ2luKCk7CiAgICAgICAgICAgIHN1bSArPSBlZGdlc1twb3NdLnNlY29uZDsKICAgICAgICAgICAgclt4XSA9IHN1bTsKICAgICAgICB9CiAgICAgICAgc3VtID0gTExPTkdfTUFYOwogICAgICAgIHdoaWxlICh4ICE9IC0xKSB7CiAgICAgICAgICAgIGxsIGRpZmYgPSBtYXgobFt4XSwgclt4XSk7CiAgICAgICAgICAgIGlmIChzdW0gPj0gZGlmZikgewogICAgICAgICAgICAgICAgaWYgKHN1bSA9PSBkaWZmKQogICAgICAgICAgICAgICAgICAgIGFucyA9IG1pbihhbnMsIHgpOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIGFucyA9IHg7CiAgICAgICAgICAgICAgICBzdW0gPSBkaWZmOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHggPSBwYXJbeF07CiAgICAgICAgfQogICAgICAgIHByaW50ZigiJWQgJWxsZFxuIiwgYW5zKzEsIHN1bSk7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==