#include <bits/stdc++.h>
#define in(t) cin >> t
#define in1(k, l) cin >> k >> l
#define ll long long
#define pb push_back
#define mk make_pair
#define pi pair<int, int>
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define fi first
#define se second
using namespace std;
const int N = 5e4 + 4;
int w[N], deg[N];
bool cmp(pair < int, pi > a, pair < int, pi> b) {
if(a.fi != b.fi) return a.fi < b.fi;
if(a.se.fi != b.se.fi) return a.se.fi > b.se.fi;
if(a.se.se != b.se.se) return a.se.se > b.se.se;
}
int get(int cur) {
if(cur == w[cur]) return cur;
return w[cur] = get(w[cur]);
}
void merge(int a, int b) {
if(rand() % 2) {
swap(a, b);
}
a = get(a);
b = get(b);
w[a] = b;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i <= n; i++) {
w[i] = i;
deg[i] = 0;
}
vector < pair < int, pi > > v, mst;
for(int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
v.pb({c, {max(a, b), min(a, b)}});
}
sort(v.begin(), v.end(), cmp);
ll ans = 0;
for(int i = 0; i < m; i++) {
int p1 = get(v[i].se.fi);
int p2 = get(v[i].se.se);
if(p1 == p2) continue;
merge(v[i].se.fi, v[i].se.se);
mst.pb(v[i]);
ans += v[i].fi;
}
printf("%lld\n", ans);
for(int i = 0; i < mst.size(); i++) {
deg[mst[i].se.fi]++;
deg[mst[i].se.se]++;
}
for(int i = 1; i <= n; i++) {
printf("%d ", deg[i]);
}
cout << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgaW4odCkgIGNpbiA+PiB0CiNkZWZpbmUgaW4xKGssIGwpIGNpbiA+PiBrID4+IGwKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtayBtYWtlX3BhaXIKI2RlZmluZSBwaSBwYWlyPGludCwgaW50PgojZGVmaW5lIGZvcm4oaSwgbikgZm9yIChpbnQgaSA9IDA7IGkgPCAoaW50KShuKTsgKytpKQojZGVmaW5lIGZvcjEoaSwgbikgZm9yIChpbnQgaSA9IDE7IGkgPD0gKGludCkobik7ICsraSkKI2RlZmluZSBmb3JkKGksIG4pIGZvciAoaW50IGkgPSAoaW50KShuKSAtIDE7IGkgPj0gMDsgLS1pKQojZGVmaW5lIGZvcmUoaSwgYSwgYikgZm9yIChpbnQgaSA9IChpbnQpKGEpOyBpIDw9IChpbnQpKGIpOyArK2kpCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IE4gPSA1ZTQgKyA0OwppbnQgd1tOXSwgZGVnW05dOwpib29sIGNtcChwYWlyIDwgaW50LCBwaSA+IGEsIHBhaXIgPCBpbnQsIHBpPiBiKSB7CglpZihhLmZpICE9IGIuZmkpIHJldHVybiBhLmZpIDwgYi5maTsKCWlmKGEuc2UuZmkgIT0gYi5zZS5maSkgcmV0dXJuIGEuc2UuZmkgPiBiLnNlLmZpOwoJaWYoYS5zZS5zZSAhPSBiLnNlLnNlKSByZXR1cm4gYS5zZS5zZSA+IGIuc2Uuc2U7Cn0KaW50IGdldChpbnQgY3VyKSB7CglpZihjdXIgPT0gd1tjdXJdKSByZXR1cm4gY3VyOwoJcmV0dXJuIHdbY3VyXSA9IGdldCh3W2N1cl0pOwp9CnZvaWQgbWVyZ2UoaW50IGEsIGludCBiKSB7CglpZihyYW5kKCkgJSAyKSB7CgkJc3dhcChhLCBiKTsKCX0KCWEgPSBnZXQoYSk7CgliID0gZ2V0KGIpOwoJd1thXSA9IGI7Cn0KaW50IG1haW4oKSB7CglpbnQgdDsKCXNjYW5mKCIlZCIsICZ0KTsKCXdoaWxlKHQtLSkgewoJCWludCBuLCBtOwoJCXNjYW5mKCIlZCVkIiwgJm4sICZtKTsKCQlmb3IoaW50IGkgPSAwOyBpIDw9IG47IGkrKykgewoJCQl3W2ldID0gaTsKCQkJZGVnW2ldID0gMDsKCQl9CgkJdmVjdG9yIDwgcGFpciA8IGludCwgcGkgPiA+IHYsIG1zdDsKCQlmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CgkJCWludCBhLCBiLCBjOwoJCQlzY2FuZigiJWQlZCVkIiwgJmEsICZiLCAmYyk7CgkJCXYucGIoe2MsIHttYXgoYSwgYiksIG1pbihhLCBiKX19KTsKCQl9CgkJc29ydCh2LmJlZ2luKCksIHYuZW5kKCksIGNtcCk7CgkJbGwgYW5zID0gMDsKCQlmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CgkJCWludCBwMSA9IGdldCh2W2ldLnNlLmZpKTsKCQkJaW50IHAyID0gZ2V0KHZbaV0uc2Uuc2UpOwoJCQlpZihwMSA9PSBwMikgY29udGludWU7CgkJCW1lcmdlKHZbaV0uc2UuZmksIHZbaV0uc2Uuc2UpOwoJCQltc3QucGIodltpXSk7CgkJCWFucyArPSB2W2ldLmZpOwoJCX0KCQlwcmludGYoIiVsbGRcbiIsIGFucyk7CgkJZm9yKGludCBpID0gMDsgaSA8IG1zdC5zaXplKCk7IGkrKykgewoJCQlkZWdbbXN0W2ldLnNlLmZpXSsrOwoJCQlkZWdbbXN0W2ldLnNlLnNlXSsrOwoJCX0KCQlmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewoJCQlwcmludGYoIiVkICIsIGRlZ1tpXSk7CgkJfQoJCWNvdXQgPDwgZW5kbDsKCX0KCXJldHVybiAwOwp9CgoK