朱刘算法模板题。
不定根，建一个虚点，向每个点连权值大于总权值的边，若最后ans-这条边的权值>总权值，说明用这样的边联通了这张图，不ok。
否则记录一下跟虚点相连的点即为根。
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#define inf 1e18
const int N=20007;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long LL;
typedef double db;
using namespace std;
int n,m,pos,pr[N],id[N],vis[N],col;
LL sum,ans,d[N];
template<typename T>void read(T &x) {
char ch=getchar(); x=0; T f=1;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}
struct edge {
int u,v,w;
edge(){}
edge(int u,int v,int w):u(u),v(v),w(w){}
}e[N];
LL solve(int rt,int V,int E) {
LL rs=0;
for(;;) {
For(i,0,V-1) d[i]=inf;
For(i,1,E) {
int u=e[i].u,v=e[i].v;
if(u!=v&&d[v]>e[i].w) {
d[v]=e[i].w;
pr[v]=u;
if(u==rt) pos=i;
}
}
For(i,0,V-1) if(i!=rt&&d[i]==inf) return -1;
d[rt]=0;
memset(id,-1,sizeof(id));
memset(vis,-1,sizeof(vis));
col=0;
For(i,0,V-1) {
int x=i; rs+=d[x];
while(id[x]==-1&&x!=rt&&vis[x]!=i) {
vis[x]=i; x=pr[x];
}
if(id[x]==-1&&x!=rt) {
for(int y=pr[x];y!=x;y=pr[y]) id[y]=col;
id[x]=col++;
}
}
if(!col) break;
For(i,0,V-1) if(id[i]==-1) id[i]=col++;
For(i,1,E) {
if(id[e[i].u]!=id[e[i].v]) e[i].w-=d[e[i].v];
e[i].u=id[e[i].u];
e[i].v=id[e[i].v];
}
V=col; rt=id[rt];
}
return rs;
}
int main() {
#ifdef DEBUG
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
while(scanf("%d%d",&n,&m)==2) {
sum=0;
For(i,1,m) {
int u,v; LL w;
read(u); read(v); read(w);
e[i]=edge(u+1,v+1,w); sum+=w;
}
For(i,1,n) e[m+i]=edge(0,i,sum+1);
ans=solve(0,n+1,m+n);
if(ans==-1||ans-(sum+1)>sum) printf("impossible
");
else printf("%lld %d
",ans-sum-1,pos-m-1);
}
return 0;
}