V[m] = u;
U[m] = v;
cap[m] = 0;
cost[m] = -Cost;
next[m] = head[v];
head[v] = m++;
}
void buildGraph()
{
scanf("%d%d",&N,&M);
int u,v,c;
m = 0;
memset(head,-1,sizeof(head));
while(M--)
{
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,1,c);
addEdge(v,u,1,c);
}
addEdge(0,1,2,0);
addEdge(N,N+1,2,0);
}
void MCMF(int st,int ed)
{
queue<int> q;
memset(flow,0,sizeof(flow));
mincost = maxflow = 0;
for(;;)
{
bool inq[MAXN];
for(int i = st;i <= ed;++i) dis[i] = (i == st ? 0 : INF);
memset(inq,0,sizeof(inq));
q.push(st);
while(!q.empty())
{
int u = q.front(); q.pop();
inq[u] = 0;
for(int e = head[u];e != -1;e = next[e])
{
if(cap[e] > flow[e] && dis[u] + cost[e] < dis[V[e]])
{
dis[V[e]] = dis[u] + cost[e];
pre[V[e]] = U[e];
Edge[V[e]] = e;
if(!inq[V[e]])
{
q.push(V[e]);
inq[V[e]] = 1;
}
}
}
}//SPFA增广
if(dis[ed] == INF) break;
int delta = INF;//delta为可改进量
for(int u = ed;u != st;u = pre[u])
delta = min(delta,cap[Edge[u]] - flow[Edge[u]]);//遍历最短路径的边,并修改可改进量
for(int u = ed;u != st;u = pre[u])
{
flow[Edge[u]] += delta;//更新正向流量
flow[Edge[u] ^ 1] -= delta;//通过异或1取得反向边的序号,并更新反向流量
}
mincost += dis[ed] * delta;
maxflow += delta;
}
}
int main()
{
//freopen("in.txt","r",stdin);
buildGraph();
MCMF(0,N+1);
printf("%d/n",mincost);
return 0;
}