#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int MAXM=1e6+5;
vector <int> G1[MAXN],G2[MAXN];
int q[MAXN];
int tot;
int f[MAXN];
map <pair<int,int>,int> ma;
int vis[MAXN];
int n,m;
void dfs1(int rt)
{
	vis[rt]=1;
	for(vector<int>::iterator it=G1[rt].begin();it!=G1[rt].end();it++)
	{
		int u=*it;
		if(!vis[u]) dfs1(u); 
	}
	q[++tot]=rt;
}
void dfs2(int rt,int bl)
{
	vis[rt]=0;
	f[rt]=bl;
	for(vector<int>::iterator it=G2[rt].begin();it!=G2[rt].end();it++)
	{
		int u=*it;
		if(vis[u]) dfs2(u,bl);
	}
}
int cnt;
int head[MAXN];
struct edge
{
	int to,next,val;
}e[MAXM];
struct node
{
	int dis;
	int num;
	bool operator <(const node& a) const {return dis>a.dis;}
};
void addedge(int u,int v,int k)
{
	e[++cnt].val=k;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int dist[MAXN];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,k;
		scanf("%d%d%d",&u,&v,&k);
		ma[make_pair(u,v)]=k;
		G1[v].push_back(u);
		G2[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i]) dfs1(i);
	for(int i=n;i>=1;i--)
		if(vis[q[i]]) dfs2(q[i],q[i]);
	memset(head,-1,sizeof(head));
	memset(dist,-1,sizeof(dist));
	for(int i=1;i<=n;i++)
		for(vector<int>::iterator it=G2[i].begin();it!=G2[i].end();it++)
		{
			int u=*it;
			if(f[i]!=f[u]) addedge(f[i],f[u],ma[make_pair(i,u)]);
		}
	priority_queue <node> q;
	node st;
	st.num=f[1];
	st.dis=0;
	dist[f[1]]=0;
	q.push(st);
	while(!q.empty())
	{
		node cur=q.top();
		q.pop();
		if(vis[cur.num])
			continue;
		for(int i=head[cur.num];i!=-1;i=e[i].next)
		{
			int v=e[i].to;
			if(dist[v]==-1||dist[v]>dist[cur.num]+e[i].val)
			{
				dist[v]=dist[cur.num]+e[i].val;
				node temp;
				temp.num=v;
				temp.dis=dist[v];
				q.push(temp);
			}
		}
	}
	printf("%d\n",dist[f[n]]);
	return 0;
}

只有第一个点没过 https://www.luogu.com.cn/record/36303791