#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,u,v,w,s,t=0,tot=0,top=0;
int dfn[50001],low[50001],stack[50001],scc[50001];
int heap[50001],dijkstra[50001];
int head[50001],to[200001],data[200001],value[200001];
bool vis[50001];
void tarjan(int now){
int next;
dfn[now]=low[now]=++t;
stack[++top]=now;
vis[now]=true;
next=head[now];
while (next!=0){
if (dfn[data[next]]==0){
tarjan(data[next]);
low[now]=min(low[now],low[data[next]]);
}
else
if (vis[data[next]])
low[now]=min(low[now],dfn[data[next]]);
next=to[next];
}
if (dfn[now]==low[now]){
while (stack[top]!=now){
vis[stack[top]]=false;
scc[stack[top]]=now;
top--;
}
vis[stack[top]]=false;
scc[stack[top]]=now;
top--;
}
}
void adjust(int now){
int next=now,minNum=dijkstra[heap[now]];
if (now*2-1<=s && dijkstra[heap[now*2-1]]<minNum){
next=now*2-1;
minNum=dijkstra[heap[now*2-1]];
}
if (now*2<=s && dijkstra[heap[now*2]]<minNum){
next=now*2;
minNum=dijkstra[heap[now*2]];
}
if (now!=next){
heap[0]=heap[now];
heap[now]=heap[next];
heap[next]=heap[0];
adjust(next);
}
}
int main(){
freopen("regexp.in","r",stdin);
freopen("regexp.out","w",stdout);
int i,j,now,next;
bool judge;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
judge=false;
next=head[u];
while (next!=0){
if (data[next]==v){
judge=true;
value[next]=min(value[next],w);
break;
}
next=to[next];
}
if (!judge){
tot++;
to[tot]=head[u];
data[tot]=v;
value[tot]=w;
head[u]=tot;
}
}
memset(vis,false,sizeof(vis));
for (i=1;i<=n;i++)
if (dfn[i]==0)
tarjan(i);
for (i=1;i<=n;i++)
heap[i]=i;
memset(dijkstra,63,sizeof(dijkstra));
dijkstra[1]=0;
s=n;
for (i=1;i<=n;i++){
now=heap[1];
heap[0]=heap[1];
heap[1]=heap[s];
heap[s]=heap[0];
s--;
next=head[now];
while (next!=0){
if (scc[now]==scc[data[next]])
value[next]=0;
dijkstra[data[next]]=min(dijkstra[data[next]],dijkstra[now]+value[next]);
next=to[next];
}
for (j=s/2;j>=1;j--)
adjust(j);
}
printf("%d\n",dijkstra[n]);
return 0;
}
网友评论