{
mem(head,-1) ;
num = 0 ;
}
int dis[Max] ;
bool vis[Max] ;
int qe[Max * 10] ;
int pre[Max] ,path[Max] ;
int spfa()
{
REP(i,0,T)dis[i] = inf ,vis[i] = 0 ;
dis[S] = 0 ;
vis[S] = 1 ;
int h = 0 , t = 0 ;
qe[h ++ ] = S ;
while( h > t )
{
int tt = qe[t ++ ] ;
vis[tt] = 0 ;
for (int i = head[tt] ;~i ;i = ed[i].next )
{
int ee = ed[i].e ;
int l = ed[i].l ;
int c = ed[i].c ;
if(l > 0 && dis[ee] > dis[tt] + c)
{
pre[ee] = tt ;
path[ee] = i ;
dis[ee] = dis[tt] + c ;
if(!vis[ee])
{
vis[ee] = 1 ;
qe[h ++ ] = ee ;
}
}
}
}
return dis[T] != inf ;
int MFMC()
{
int M = 0 ;
while(spfa())
{
int ff = inf ;
for (int i = T ;i != S ;i = pre[i])
ff = min(ff , ed[path[i]].l) ;
for (int i = T ;i != S ;i = pre[i])
ed[path[i]].l -= ff ,ed[path[i] ^ 1].l += ff ;
M += dis[T] * ff ;
}
return M ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("acm.txt", "r", stdin);
#endif
init() ;
readint(n) ;
readint(m) ;
S = 0 ,T = n + 1 ;
REP(i,0,m - 1)
{
int a , b , c ;
readint(a) ;
readint(b) ;
readint(c) ;
add(a,b,1,c) ;
add(b,a,1,c) ;
}
add(S,1,2,0) ;
add(n,T,2,0) ;
cout << MFMC() << endl;
return 0;
}