#include <iostream>
#include <vector>
#include <climits>
#include <map>
using namespace std;
struct node
{
long long a,b,x;
node(long long a1,long long b1,long long x1)
{
a=a1;
b=b1;
x=x1;
}
};
void dfs(map<long long ,map<long long,long long> >& Map,vector<long long>& visited,int i)
{
visited[i]=1;
for(auto it=Map[i].begin();it!=Map[i].end();it++)
{
if(visited[it->first] == 0)
{
dfs(Map,visited,it->first);
}
}
}
int main() {
long long n,m;
cin>>n>>m;
vector<node*> edges;
map<long long ,map<long long,long long> > Map1;
map<long long ,map<long long,long long> > Map2;
vector<long long> vis1(n,0);
vector<long long> vis2(n,0);
for(long long i=0;i<m;i++)
{
long long a,b,x;
cin>>a>>b>>x;
edges.push_back(new node(a-1,b-1,-1*x));
Map1[a-1][b-1]=1;
Map2[b-1][a-1]=1;
}
dfs(Map1,vis1,0);
dfs(Map2,vis2,n-1);
long long d[n];
for(long long i=0;i<m;i++)
{
d[i] = LLONG_MAX;
}
d[0]=0;
for(long long i=0;i<n-1;i++)
{
for(long long j=0;j<edges.size();j++)
{
long long u = edges[j]->a;
long long v = edges[j]->b;
long long w = edges[j]->x;
if(d[u] != LLONG_MAX && d[v] > d[u]+w)
{
d[v] = d[u]+w;
}
}
}
for(long long i=0;i<n;i++)
{
cout<<"d["<<i<<"]="<<d[i]<<endl;
}
long long flag=0;
for(long long j=0;j<edges.size();j++)
{
long long u = edges[j]->a;
long long v = edges[j]->b;
long long w = edges[j]->x;
if(d[v] > d[u]+w && vis1[v] && vis2[v])
{
cout<<-1<<endl;
return 0;
}
}
cout<<d[n-1]*-1<<endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y2xpbWl0cz4KI2luY2x1ZGUgPG1hcD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBub2RlCnsKCWxvbmcgbG9uZyBhLGIseDsKCW5vZGUobG9uZyBsb25nIGExLGxvbmcgbG9uZyBiMSxsb25nIGxvbmcgeDEpCgl7CgkJYT1hMTsKCQliPWIxOwoJCXg9eDE7Cgl9Cn07Cgp2b2lkIGRmcyhtYXA8bG9uZyBsb25nICxtYXA8bG9uZyBsb25nLGxvbmcgbG9uZz4gPiYgTWFwLHZlY3Rvcjxsb25nIGxvbmc+JiB2aXNpdGVkLGludCBpKQp7Cgl2aXNpdGVkW2ldPTE7Cglmb3IoYXV0byBpdD1NYXBbaV0uYmVnaW4oKTtpdCE9TWFwW2ldLmVuZCgpO2l0KyspCgl7CgkJaWYodmlzaXRlZFtpdC0+Zmlyc3RdID09IDApCgkJewoJCQlkZnMoTWFwLHZpc2l0ZWQsaXQtPmZpcnN0KTsKCQl9Cgl9Cn0KCmludCBtYWluKCkgewoKCWxvbmcgbG9uZyBuLG07CgljaW4+Pm4+Pm07CQoJdmVjdG9yPG5vZGUqPiBlZGdlczsKCW1hcDxsb25nIGxvbmcgLG1hcDxsb25nIGxvbmcsbG9uZyBsb25nPiA+IE1hcDE7CgltYXA8bG9uZyBsb25nICxtYXA8bG9uZyBsb25nLGxvbmcgbG9uZz4gPiBNYXAyOwoJdmVjdG9yPGxvbmcgbG9uZz4gdmlzMShuLDApOwoJdmVjdG9yPGxvbmcgbG9uZz4gdmlzMihuLDApOwoJZm9yKGxvbmcgbG9uZyBpPTA7aTxtO2krKykKCXsKCQlsb25nIGxvbmcgYSxiLHg7CgkJY2luPj5hPj5iPj54OwoJCWVkZ2VzLnB1c2hfYmFjayhuZXcgbm9kZShhLTEsYi0xLC0xKngpKTsKCQlNYXAxW2EtMV1bYi0xXT0xOwoJCU1hcDJbYi0xXVthLTFdPTE7Cgl9CgkKCWRmcyhNYXAxLHZpczEsMCk7CglkZnMoTWFwMix2aXMyLG4tMSk7CgkKCWxvbmcgbG9uZyBkW25dOwoJZm9yKGxvbmcgbG9uZyBpPTA7aTxtO2krKykKCXsKCQlkW2ldID0gTExPTkdfTUFYOwoJfQoJZFswXT0wOwoJZm9yKGxvbmcgbG9uZyBpPTA7aTxuLTE7aSsrKQoJewoJCWZvcihsb25nIGxvbmcgaj0wO2o8ZWRnZXMuc2l6ZSgpO2orKykKCQl7CgkJCWxvbmcgbG9uZyB1ID0gZWRnZXNbal0tPmE7CgkJCWxvbmcgbG9uZyB2ID0gZWRnZXNbal0tPmI7CgkJCWxvbmcgbG9uZyB3ID0gZWRnZXNbal0tPng7CgkJCQoJCQlpZihkW3VdICE9IExMT05HX01BWCAmJiBkW3ZdID4gZFt1XSt3KQoJCQl7CgkJCQlkW3ZdID0gZFt1XSt3OwoJCQl9CgkJfQoJfQoJCglmb3IobG9uZyBsb25nIGk9MDtpPG47aSsrKQoJewoJCWNvdXQ8PCJkWyI8PGk8PCJdPSI8PGRbaV08PGVuZGw7Cgl9CgkKCWxvbmcgbG9uZyBmbGFnPTA7Cglmb3IobG9uZyBsb25nIGo9MDtqPGVkZ2VzLnNpemUoKTtqKyspCgl7CgkJbG9uZyBsb25nIHUgPSBlZGdlc1tqXS0+YTsKCQlsb25nIGxvbmcgdiA9IGVkZ2VzW2pdLT5iOwoJCWxvbmcgbG9uZyB3ID0gZWRnZXNbal0tPng7CgkJCgkJaWYoZFt2XSA+IGRbdV0rdyAmJiB2aXMxW3ZdICYmIHZpczJbdl0pCgkJewoJCQljb3V0PDwtMTw8ZW5kbDsKCQkJcmV0dXJuIDA7CgkJfQoJfQoKCWNvdXQ8PGRbbi0xXSotMTw8ZW5kbDsKCglyZXR1cm4gMDsKfQ==