题意:有n个节点，m个用电器。之后输入m行每行三个整数a,b,c;
节点a为正极(或者a 为 '+'即总的正极)，b为该用电器的负极(b = '-'表示总的负极)，c为该用电器要正常工作最小的电流；
问要使得该电路中的所有的电器都工作，总正极至少输入多大的电流?如果不存在方案，输出impossible;
思路:将下界归零后使用超级源点和汇点平衡流量，跑最大流之后，加一条题目的源点0和汇点n+1，即总正极和总负极连一条反向的容量为inf的边，再次跑最大流；
如果满足流量平衡，则添加的反向边的流量就是从总正极流出的符合要求的最小电流；
ps: 对于原理不是很懂，没能想明白；下面写下粗糙的想法；
第一次跑最大流，求出的不是从题给源点到题给汇点的流量，只是先平衡些流量。使得连边之后，再次跑最大流，从题给源点流出的流量最小；
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
typedef pair<int,int> PII;
#define A first
#define B second
#define MK make_pair
typedef long long ll;
typedef unsigned int uint;
int s,t,n,m;
template<typename T>
void read1(T &m)
{
T x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-'){m = n+; return ;}if(ch == '+'){m = ;return ;} ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>) out(a/);
putchar(a%+'');
}
int T,kase = ,i,j,k;
#define N 55
#define M 1000
int head[N],tot;
struct Edge{
int from,to,cap,flow,Next;
Edge(){}
Edge(int f,int to,int cap,int Next):from(f),to(to),cap(cap),Next(Next),flow(){}
}e[M<<];
inline void ins(int u,int v,int cap)
{
//cout<<u<<" "<<v<<" "<<cap<<endl;
e[++tot] = Edge{u,v,cap,head[u]};
head[u] = tot;
}
int sum[N];
int vis[N], cur[N],d[N];
queue<int> Q;
int BFS()
{
rep1(i,,t) vis[i] = ;
vis[s] = ;d[s] = ;
Q.push(s);
while(!Q.empty()){
int u = Q.front();Q.pop();
for(int i = head[u];i;i = e[i].Next){
int v = e[i].to;
if(!vis[v] && e[i].cap > e[i].flow){ // 只考虑残量网络的弧
vis[v] = ;
d[v] = d[u] + ;
Q.push(v);
}
}
}
return vis[t];
}
int DFS(int x,int a)// a表示目前为所有弧的最小残量
{
if(x == t || a == ) return a;
int flow = , f;
for(int& i = cur[x];i;i = e[i].Next){// 从上次考虑的弧开始
int v = e[i].to;
if(d[v] == d[x]+ && (f = DFS(v,min(a,e[i].cap - e[i].flow))) > ){
e[i].flow += f;
e[i^].flow -= f;
flow += f;
a -= f;// 残量-流量
if(a == ) break;
}
}
return flow;
}
int Dinic()
{
int flow = ;
while(BFS()){//在残量网络基础上不断刷新层次图;
rep1(i,,t) cur[i] = head[i];//记录当前探索到的点的弧的编号
flow += DFS(s,inf);
}
return flow;
}
int main()
{
//freopen("data.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&m) == && n+m){
MS0(sum);MS0(head);tot = ;
s = n+, t = n + ;
int u,v,w;
rep0(i,,m){
read3(u,v,w);
sum[u] -= w, sum[v] += w;
ins(u,v,inf);ins(v,u,);
}
rep0(i,,s){
if(sum[i] > ) ins(s,i,sum[i]),ins(i,s,);
if(sum[i] < ) ins(i,t,-sum[i]),ins(t,i,);
}
int flow = Dinic();
ins(n+,,inf);ins(,n+,);
Dinic();
bool flag = true;
for(int d = head[s];d;d = e[d].Next){
if(e[d].cap - e[d].flow){
flag = false;
break;
}
}
for(int d = head[n+];d;d = e[d].Next) // 是否满足流量平衡;
if(e[d].to == ){
flow = e[d].flow;break;
}
if(!flag) puts("impossible");
else printf("%d\n",flow);
}
return ;
}