思路：

很普通很普通的一道差分约束。。 就是Dijkstra的时候要进行堆优化

// by SiriusRen#include 
     
      #include 
      
       #define N 150050using namespace std;int n,m,xx,yy,zz,tot=1;int first[30050],next[N],w[N],v[N],dis[30050];bool vis[30050];struct node{
    int at,weight;}jy,temp;priority_queue
       
        pq;bool operator <(node a,node b){
    return a.weight>b.weight;}void add(int x,int y,int z){    w[tot]=z;v[tot]=y;    next[tot]=first[x];first[x]=tot++;}void Dijkstra(){    jy.at=1;jy.weight=0;    pq.push(jy);    while(!pq.empty()){        jy=pq.top(),pq.pop();        if(vis[jy.at])continue;        vis[jy.at]=1;dis[jy.at]=jy.weight;        for(int i=first[jy.at];i;i=next[i]){            if(vis[v[i]])continue;            temp.at=v[i],temp.weight=jy.weight+w[i];            pq.push(temp);        }    }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++)scanf("%d%d%d",&xx,&yy,&zz),add(xx,yy,zz);    Dijkstra();    printf("%d\n",dis[n]);}