#include<fstream>
#include<vector>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
struct nod
{
    int x;
    int c;
}s;
vector <nod> l[1001];
int n,m,i,j,x,y,t,s1,s2;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>s.x>>s.c;
        l[x].push_back(s);
        y=s.x;
        s.x=x;
        l[y].push_back(s);
    }
    for(i=0;i<l[1].size();i++)
    s1+=l[1][i].c;
    for(i=0;i<l[n].size();i++)
    s2+=l[n][i].c;
    g<<min(s1,s2);
    return 0;
}