#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> a[100];
int da[100];
int visina[100];

int main()
{
    int h;
    cin>>h;
    int n;
    cin>>n;
    int i;
    for(i=0;i<n;i++){
        da[i]=0;
    }
    int s,c,raz;
    for(i=0;i<n-1;i++){
        cin>>s>>c>>raz;
        a[s].push_back({c,raz});
        (da[s])++;
    }
    queue<int> za_obradu;
    visina[0]=h;
    za_obradu.push(0);
    int trenutni;
    while(!za_obradu.empty()){
        trenutni=za_obradu.front();
        za_obradu.pop();
        //kod neusmerenog slicnog grafa mora pitanje da li je obidjen
        for(i=0;i<da[trenutni];i++){
            visina[a[trenutni][i].first]=visina[trenutni]+a[trenutni][i].second;
            za_obradu.push(a[trenutni][i].first);
        }
    }

    int minn=h;
    for(i=0;i<n;i++){
        if(visina[i]<minn){
            minn=visina[i];
        }
    }
    cout<<minn<<endl;
    return 0;
}
