37分蒟蒻

#include<bits/stdc++.h>
using namespace std;
struct stu{ int y,q; };
int n,m,in[1505],out[1505],dis[1505];
vector<stu> a[1505];
queue<int> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		in[u]++;
		stu tmp={v,w};
		a[u].push_back(tmp); //建图
	}
	for(int i=2;i<=n;i++) if(!in[i]){
		dis[i]=INT_MIN; 
		q.push(i);
	}
	q.push(1);
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=0;i<a[x].size();i++){
			dis[a[x][i].y]=max(dis[x]+a[x][i].q,dis[a[x][i].y]);
			if(--in[a[x][i].q]==0) q.push(a[x][i].q); //入度--，如果入度为0，q.push(a[x][i].q)。
		}
	}
	if(dis[n]!=INT_MIN) cout<<dis[n];
	else cout<<-1;
	return 0;
}