#include <bits/stdc++.h>
typedef long long ll;
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define FOR(i,a,b) for( ll i = (ll)(a); i <= (ll)(b); i++ )
#define ROF(i,a,b) for( ll i = (ll)(a); i >= (ll)(b); i-- )
#define debug(x) cerr << "[DEBUG] " << #x << " = " << x << endl;
#define matrix vector< vector<ll> >
#define F first
#define S second
#define mp make_pair
#define INPFILE freopen("input.in","r",stdin)
#define OUTFILE freopen("output.out","w",stdout)
#define BOOST ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std;
ll parent[70];
ll ans[70];
set<tuple<ll,ll,ll>> rules;
ll find(ll x) {
if(x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
void join(ll x, ll y) {
ll p = find(x);
ll q = find(y);
if(p == q) return;
parent[p] = q;
}
void reset() {
FOR(i,0,69) parent[i] = i;
}
bool rec(set<ll> Q, ll last) {
//debug(last);
//for(ll x : Q) cerr << x << ' ';
//cerr << '\n';
if(Q.empty()) return true;
set<tuple<ll,ll,ll>> v;
for(auto p : rules) {
ll x = get<0>(p);
ll y = get<1>(p);
ll z = get<2>(p);
bool hasx = Q.find(x) != Q.end();
bool hasy = Q.find(y) != Q.end();
bool hasz = Q.find(z) != Q.end();
if(hasz && (!hasx || !hasy)) return false;
else if(hasz || (hasx && hasy)) v.insert(p);
}
for(ll cur : Q) {
reset();
bool pos = true;
for(auto p : v) {
ll x = get<0>(p);
ll y = get<1>(p);
ll z = get<2>(p);
if(cur != z) {
join(x, z);
join(y, z);
}
if((cur == x || cur == y) && cur != z) {
pos = false;
break;
}
}
for(auto p : v) {
ll x = get<0>(p);
ll y = get<1>(p);
ll z = get<2>(p);
if(cur == z && find(x) == find(y)) {
pos = false;
break;
}
}
if(pos) {
map<ll,set<ll>> grp;
for(ll x : Q) if(x != cur) {
grp[find(x)].insert(x);
}
ans[cur] = last;
bool ret = true;
for(auto it : grp) {
ret &= rec(it.S, cur);
}
return ret;
}
}
return false;
}
int main() {
ll _t, _c = 1; cin >> _t;
while(_t--) {
FOR(i,0,69) ans[i] = -1;
rules.clear();
ll n, m;
cin >> n >> m;
while(m--) {
ll x, y, z;
cin >> x >> y >> z;
rules.insert({min(x,y), max(x,y), z});
}
set<ll> Q;
FOR(i,1,n) Q.insert(i);
bool ret = rec(Q, 0);
cout << "Case #" << _c++ << ": ";
if(!ret) {
cout << "Impossible\n";
} else {
FOR(i,1,n) cout << ans[i] << ' ';
cout << '\n';
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnR5cGVkZWYgbG9uZyBsb25nIGxsOwojZGVmaW5lIGFsbChjKSAoYykuYmVnaW4oKSwgKGMpLmVuZCgpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgRk9SKGksYSxiKSBmb3IoIGxsIGkgPSAobGwpKGEpOyBpIDw9IChsbCkoYik7IGkrKyApCiNkZWZpbmUgUk9GKGksYSxiKSBmb3IoIGxsIGkgPSAobGwpKGEpOyBpID49IChsbCkoYik7IGktLSApCiNkZWZpbmUgZGVidWcoeCkgY2VyciA8PCAiW0RFQlVHXSAiIDw8ICN4IDw8ICIgPSAiIDw8IHggPDwgZW5kbDsKI2RlZmluZSBtYXRyaXggdmVjdG9yPCB2ZWN0b3I8bGw+ID4KI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBJTlBGSUxFIGZyZW9wZW4oImlucHV0LmluIiwiciIsc3RkaW4pCiNkZWZpbmUgT1VURklMRSBmcmVvcGVuKCJvdXRwdXQub3V0IiwidyIsc3Rkb3V0KQojZGVmaW5lIEJPT1NUIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKE5VTEwpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpsbCBwYXJlbnRbNzBdOwpsbCBhbnNbNzBdOwpzZXQ8dHVwbGU8bGwsbGwsbGw+PiBydWxlczsKCmxsIGZpbmQobGwgeCkgewogIGlmKHggPT0gcGFyZW50W3hdKSByZXR1cm4geDsKICByZXR1cm4gcGFyZW50W3hdID0gZmluZChwYXJlbnRbeF0pOwp9Cgp2b2lkIGpvaW4obGwgeCwgbGwgeSkgewogIGxsIHAgPSBmaW5kKHgpOwogIGxsIHEgPSBmaW5kKHkpOwoKICBpZihwID09IHEpIHJldHVybjsKCiAgcGFyZW50W3BdID0gcTsKfQoKdm9pZCByZXNldCgpIHsKICBGT1IoaSwwLDY5KSBwYXJlbnRbaV0gPSBpOwp9Cgpib29sIHJlYyhzZXQ8bGw+IFEsICBsbCBsYXN0KSB7CiAgLy9kZWJ1ZyhsYXN0KTsKICAvL2ZvcihsbCB4IDogUSkgY2VyciA8PCB4IDw8ICcgJzsKICAvL2NlcnIgPDwgJ1xuJzsKICBpZihRLmVtcHR5KCkpIHJldHVybiB0cnVlOwogIHNldDx0dXBsZTxsbCxsbCxsbD4+IHY7CiAgZm9yKGF1dG8gcCA6IHJ1bGVzKSB7CiAgICBsbCB4ID0gZ2V0PDA+KHApOwogICAgbGwgeSA9IGdldDwxPihwKTsKICAgIGxsIHogPSBnZXQ8Mj4ocCk7CgogICAgYm9vbCBoYXN4ID0gUS5maW5kKHgpICE9IFEuZW5kKCk7CiAgICBib29sIGhhc3kgPSBRLmZpbmQoeSkgIT0gUS5lbmQoKTsKICAgIGJvb2wgaGFzeiA9IFEuZmluZCh6KSAhPSBRLmVuZCgpOwoKICAgIGlmKGhhc3ogJiYgKCFoYXN4IHx8ICFoYXN5KSkgcmV0dXJuIGZhbHNlOwogICAgZWxzZSBpZihoYXN6IHx8IChoYXN4ICYmIGhhc3kpKSB2Lmluc2VydChwKTsKICB9CgogIGZvcihsbCBjdXIgOiBRKSB7CiAgICByZXNldCgpOwogICAgYm9vbCBwb3MgPSB0cnVlOwogICAgZm9yKGF1dG8gcCA6IHYpIHsKICAgICAgbGwgeCA9IGdldDwwPihwKTsKICAgICAgbGwgeSA9IGdldDwxPihwKTsKICAgICAgbGwgeiA9IGdldDwyPihwKTsKCiAgICAgIGlmKGN1ciAhPSB6KSB7CiAgICAgICAgam9pbih4LCB6KTsKICAgICAgICBqb2luKHksIHopOwogICAgICB9CiAgICAgIGlmKChjdXIgPT0geCB8fCBjdXIgPT0geSkgJiYgY3VyICE9IHopIHsKICAgICAgICBwb3MgPSBmYWxzZTsKICAgICAgICBicmVhazsKICAgICAgfQogICAgfQogICAgZm9yKGF1dG8gcCA6IHYpIHsKICAgICAgbGwgeCA9IGdldDwwPihwKTsKICAgICAgbGwgeSA9IGdldDwxPihwKTsKICAgICAgbGwgeiA9IGdldDwyPihwKTsKCiAgICAgIGlmKGN1ciA9PSB6ICYmIGZpbmQoeCkgPT0gZmluZCh5KSkgewogICAgICAgIHBvcyA9IGZhbHNlOwogICAgICAgIGJyZWFrOwogICAgICB9CiAgICB9CgogICAgaWYocG9zKSB7CiAgICAgIG1hcDxsbCxzZXQ8bGw+PiBncnA7CiAgICAgIGZvcihsbCB4IDogUSkgaWYoeCAhPSBjdXIpIHsKICAgICAgICBncnBbZmluZCh4KV0uaW5zZXJ0KHgpOwogICAgICB9CiAgICAgIGFuc1tjdXJdID0gbGFzdDsKICAgICAgYm9vbCByZXQgPSB0cnVlOwogICAgICBmb3IoYXV0byBpdCA6IGdycCkgewogICAgICAgIHJldCAmPSByZWMoaXQuUywgY3VyKTsKICAgICAgfQogICAgICByZXR1cm4gcmV0OwogICAgfQogIH0KCiAgcmV0dXJuIGZhbHNlOwp9CgppbnQgbWFpbigpIHsKICBsbCBfdCwgX2MgPSAxOyBjaW4gPj4gX3Q7CiAgd2hpbGUoX3QtLSkgewogICAgRk9SKGksMCw2OSkgYW5zW2ldID0gLTE7CiAgICBydWxlcy5jbGVhcigpOwogICAgbGwgbiwgbTsKICAgIGNpbiA+PiBuID4+IG07CgogICAgd2hpbGUobS0tKSB7CiAgICAgIGxsIHgsIHksIHo7CiAgICAgIGNpbiA+PiB4ID4+IHkgPj4gejsKICAgICAgcnVsZXMuaW5zZXJ0KHttaW4oeCx5KSwgbWF4KHgseSksIHp9KTsKICAgIH0KCiAgICBzZXQ8bGw+IFE7CiAgICBGT1IoaSwxLG4pIFEuaW5zZXJ0KGkpOwoKICAgIGJvb2wgcmV0ID0gcmVjKFEsIDApOwogICAgY291dCA8PCAiQ2FzZSAjIiA8PCBfYysrIDw8ICI6ICI7CiAgICBpZighcmV0KSB7CiAgICAgIGNvdXQgPDwgIkltcG9zc2libGVcbiI7CiAgICB9IGVsc2UgewogICAgICBGT1IoaSwxLG4pIGNvdXQgPDwgYW5zW2ldIDw8ICcgJzsKICAgICAgY291dCA8PCAnXG4nOwogICAgfQogIH0KfQ==