#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 200+10;
int n, m; //n个顶点 m条边
int in[200+5], out[200+5];
struct Dinic
{
int n; //n个顶点
struct edge
{
int from, to, cap;
};
vector<int> G[maxn];
vector e;
int level[maxn], iter[maxn];
void init()
{
for(int i=0; i<=n; i++) G[i].clear();
e.clear();
}
void add_edge(int u, int v, int cap)
{
e.push_back((edge){u, v, cap});
e.push_back((edge){v, u, 0});
int m = e.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
void bfs(int s)
{
memset(level, -1, sizeof(level));
queue<int> que;
level[s] = 0;
que.push(s);
while(!que.empty())
{
int u = que.front();
que.pop();
for(int i=0; i)
{
edge &te = e[G[u][i]];
if(te.cap>0 && level[te.to]<0)
{
level[te.to] = level[u] + 1;
que.push(te.to);
}
}
}
}
int dfs(int v, int t, int f)
{
if(v == t) return f;
for(int &i=iter[v]; i)
{
edge &tpe = e[G[v][i]];
if(tpe.cap>0 && level[v]<level[tpe.to])
{
int d = dfs(tpe.to, t, min(f, tpe.cap));
if(d > 0)
{
tpe.cap -= d;
e[G[v][i]^1].cap += d;
return d;
}
}
}
return 0;
}
int max_flow(int s, int t)
{
int flow = 0;
for(;;)
{
bfs(s);
if(level[t]<0) return flow;
memset(iter, 0, sizeof(iter));
int f;
while((f=dfs(s, t, 0x3fffffff)) > 0)
flow += f;
}
}
} di;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m); //0超级源点 n+1超级汇点
di.n = n+2;
di.init();
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
for(int i=0; i)
{
int u, v, t;
scanf("%d%d%d", &u, &v, &t);
in[v]++; out[u]++;
if(t == 0) di.add_edge(u, v, 1);
}
bool flog = true;
for(int i=1; i<=n&&flog; i++)
if(abs(in[i]-out[i])%2 != 0) flog=false;
if(!flog)
{
printf("impossible\n");
continue;
}
for(int i=1; i<=n; i++)
{
if(in[i]<out[i])
di.add_edge(0, i, (out[i]-in[i])/2);
else if(in[i]>out[i])
di.add_edge(i, n+1, (in[i]-out[i])/2);
}
di.max_flow(0, n+1);
flog = true;
for(int i=0; i2)
{
if(di.e[i].from==0 && di.e[i].cap!=0) flog=false;
}
if(flog) printf("possible\n");
else printf("impossible\n");
}
return 0;
}