#include <cstdio>#include <cstring>#define MAXN 1005#define MAXM 10005#define INF 0x3f3f3f3fstruct Edge{    int y,c,w,ne;//c容量 w费用}e[MAXM*4];int n,m,x,y,w;int s,t,Maxflow,Mincost;int all,be[MAXN];int q[MAXM*4],dis[MAXN],pre[MAXN];//pre存的是当前点的前边bool vis[MAXN];void add(int x, int y, int c, int cost){    e[all].y=y;e[all].c=c;e[all].w=cost;    e[all].ne=be[x];    be[x]=all++;    e[all].y=x;e[all].c=0;e[all].w=-cost;//反向边费用取负    e[all].ne=be[y];    be[y]=all++;}void init(){    all=0;    memset(be,-1,sizeof(be));}bool spfa(int s, int t){    for(int i=0; i<MAXN; i++)    {        dis[i]=INF;        vis[i]=0;        pre[i]=-1;    }    dis[s]=0;    vis[s]=1;    int head=0,tail=0;    q[++tail]=s;    while(head<tail)    {        int u=q[++head];        vis[u]=0;        for(int i=be[u]; i!=-1; i=e[i].ne)        {            int v=e[i].y;            if(e[i].c>0 && dis[v]>dis[u]+e[i].w)            {                dis[v]=dis[u]+e[i].w;                pre[v]=i;                if(!vis[v])                {                    vis[v]=1;                    q[++tail]=v;                }            }        }    }    if(pre[t]==-1) return 0;    return 1;}void MincostMaxflow(int s, int t){    Maxflow=0;    Mincost=0;    while(spfa(s,t))    {        int minc=INF;        for(int i=pre[t]; i!=-1; i=pre[e[i^1].y])            if(minc>e[i].c) minc=e[i].c;        for(int i=pre[t]; i!=-1; i=pre[e[i^1].y])        {            e[i].c-=minc;            e[i^1].c+=minc;            Mincost+=e[i].w*minc;        }        Maxflow+=minc;    }}int main(){    scanf("%d%d",&n,&m);    init();    s=n+1;    t=n+2;    for(int i=0; i<m; i++)    {        scanf("%d%d%d",&x,&y,&w);        add(x,y,1,w);        add(y,x,1,w);    }    add(s,1,2,0);    add(n,t,2,0);    MincostMaxflow(s,t);    printf("%d\n",Mincost);    return 0;}