建个图，套个模板。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
#define INF 0x3ffffff
struct node
{
int u,v,next,re,w;
}edge[];
int first[],dis[];
int in[],out[];
int t,str,end;
void CL()
{
t = ;
memset(first,-,sizeof(first));
}
void add(int u,int v,int w)
{
edge[t].u = u;
edge[t].v = v;
edge[t].w = w;
edge[t].re = t + ;
edge[t].next = first[u];
first[u] = t ++;
edge[t].u = v;
edge[t].v = u;
edge[t].w = ;
edge[t].re = t - ;
edge[t].next = first[v];
first[v] = t ++;
}
int bfs()
{
int u,v,i;
memset(dis,-,sizeof(dis));
queue<int> que;
que.push(str);
dis[str] = ;
while(!que.empty())
{
u = que.front();
que.pop();
for(i = first[u];i != -;i = edge[i].next)
{
v = edge[i].v;
if(edge[i].w > &&dis[v] < )
{
dis[v] = dis[u] + ;
que.push(v);
}
}
}
if(dis[end] > ) return ;
else return ;
}
int dfs(int u,int step)
{
int i,temp,v,tf = ;
if(u == end) return step;
for(i = first[u];i != -;i = edge[i].next)
{
v = edge[i].v;
if(edge[i].w > &&dis[v] == dis[u] + &&(temp = dfs(v,min(step,edge[i].w))))
{
edge[i].w -= temp;
edge[edge[i].re].w += temp;
return temp;
}
}
if(!tf) dis[u] = -;
return tf;
}
int main()
{
int t,i,u,v,k,n,m;
scanf("%d",&t);
while(t--)
{
memset(in,,sizeof(in));
memset(out,,sizeof(out));
scanf("%d%d",&n,&m);
CL();
str = ;
end = n + ;
for(i = ;i < m;i ++)
{
scanf("%d%d%d",&u,&v,&k);
in[u] ++;
out[v] ++;
if(k != )
add(u,v,);
}
for(i = ;i <= n;i ++)
{
if(abs(in[i]-out[i])% == )
break;
}
if(i != n+)
{
printf("impossible\n");
continue;
}
int sum = ;
for(i = ;i <= n;i ++)
{
if(in[i] > out[i])
{
add(str,i,(in[i]-out[i])/);
sum += (in[i]-out[i])/;
}
else
{
add(i,end,(out[i]-in[i])/);
}
}
int ans = ,res;
while(bfs())
{
while(res = dfs(str,INF))
ans += res;
}
if(ans == sum)
printf("possible\n");
else
printf("impossible\n");
}
return ;
}