28分，AC#4#10#11

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int rud[1505],ans[1505];
int v[1505][1505];
int main()
{
	int n,m;
	cin>>n>>m;
	queue<int> q;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	v[i][j]=-100001;
	for(int i=1;i<=m;i++)
	{
		int u,t,w;
		cin>>u>>t>>w;
		v[u][t]=max(v[u][t],w);
		v[u][0]++;
		rud[t]++;
	}
	for(int i=1;i<=n;i++)
	if(rud[i]==0)
	q.push(i);
	while(!q.empty())
	{
		int chl=q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(v[chl][i]==-100001)
			continue;
			ans[i]=max(ans[i],v[chl][i]+ans[chl]);
			rud[i]--;
			if(rud[i]==0)
			q.push(i);
		}
	}
	cout<<ans[n];
	return 0;
}