这个题就是需要求整个有向带权图的最小树形图，没有指定根，那就需要加一个虚根
这个虚根到每个点的权值是总权值+1，然后就可以求了，如果求出来的权值大于等于二倍的总权值，就无解
有解的情况，还需要输出最根，多解的情况，肯定是某个环上所有的点为根都可以（比如所有的点构成一个环），
这样加边的时候虚边的时候按照点的标号从小到大编，这样第一个以虚根为前驱的点也是最小的点就可以标记（标记一下）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N=2e3+;
const LL INF=0x7fffffff;
struct Edge{
int u,v;
LL w;
}edge[N*N];
LL in[N];
int id[N],vis[N],pre[N],n,m,pos;
LL zhuliu(int rt,int n,int m){
LL ret=;
while(){
for(int i=;i<=n;++i)in[i]=INF;
for(int i=;i<=m;++i){
if(edge[i].u!=edge[i].v&&edge[i].w<in[edge[i].v]){
if(edge[i].u==rt)pos=i;
pre[edge[i].v]=edge[i].u;
in[edge[i].v]=edge[i].w;
}
}
for(int i=;i<=n;++i)
if(i!=rt&&in[i]==INF)return -;
int cnt=-;
memset(id,-,sizeof(id));
memset(vis,-,sizeof(vis));
in[rt]=;
for(int i=;i<=n;++i){
ret+=in[i];
int v=i;
while(vis[v]!=i&&id[v]==-&&v!=rt){
vis[v]=i;
v=pre[v];
}
if(v!=rt&&id[v]==-){
++cnt;
for(int u=pre[v];u!=v;u=pre[u])
id[u]=cnt;
id[v]=cnt;
}
}
if(cnt==-)break;
for(int i=;i<=n;++i)
if(id[i]==-)id[i]=++cnt;
for(int i=;i<=m;++i){
int u=edge[i].u,v=edge[i].v;
edge[i].u=id[u];
edge[i].v=id[v];
if(id[u]!=id[v])edge[i].w-=in[v];
}
n=cnt;
rt=id[rt];
}
return ret;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
LL sum=;
for(int i=;i<=m;++i){
scanf("%d%d%I64d",&edge[i].u,&edge[i].v,&edge[i].w);
++edge[i].u,++edge[i].v;
sum+=edge[i].w;
}
++sum;
for(int i=m+;i<=m+n;++i){
edge[i].u=,edge[i].v=i-m;
edge[i].w=sum;
}
LL ans=zhuliu(,n,n+m);
if(ans-sum>=sum)printf("impossible\n\n");
else printf("%I64d %d\n\n",ans-sum,pos-m-);
}
return ;
}