tioj 1509

using namespace std;
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <memory.h>
#include <set>
#include <string>

#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define LL long long

/*
8e7 so dian
FHVirus so dian
youou so dian
KYW so dian
hubert so dian
jass so dian
tingyu so dian
*/

//IO
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
#define endl '\n'

//workspace
vector <pii> out[1000100],ret[1000100];
int dis[1000100];

int main(){
    theyRSOOOOOOOOODIAN
    int m,n;

    cin >> m >> n;
    for (int i=0;i<n;++i){
        int p,q,r;

        cin >> p >> q >> r;
        out[p].pb({q,r});
        ret[q].pb({p,r});
    }
    for (int i=1;i<=m;++i)
        dis[i] = 1e9+10;

    int relaxed = 1;
    pii cur;
    dis[1] = 0;
    priority_queue <pii,vector<pii>,greater<pii>> pq;
    pq.push({0,1});

    for (int i=0;i<m;++i){
        do{
            cur = pq.top();
            pq.pop();
        }while (pq.size() && cur.F > dis[cur.S]);

        for (auto i:out[cur.S]){
            if (dis[i.F] > cur.F + i.S){
                dis[i.F] = cur.F + i.S;
                pq.push({dis[i.F],i.F});
            }
        }
    }

    int ans = 0;
    for (int i=1;i<=m;++i){
        if (dis[i] == 1e9+10){
            cout << '0';
            return 0;
        }
        ans += dis[i],dis[i] = 1e9+10;
    }
    while (pq.size())
        pq.pop();
    dis[1] = 0;
    pq.push({0,1});

    for (int i=0;i<m;++i){
        do{
            cur = pq.top();
            pq.pop();
        }while (pq.size() && cur.F > dis[cur.S]);

        for (auto i:ret[cur.S]){
            if (dis[i.F] > cur.F + i.S){
                dis[i.F] = cur.F + i.S;
                pq.push({dis[i.F],i.F});
            }
        }
    }

    for (int i=1;i<=m;++i){
        if (dis[i] == 1e9+10){
            ans = 0;
            break;
        }
        ans += dis[i];
    }

    cout << ans;

    return 0;
}