**两种方法存图，分别使用邻接矩阵和链式前向星****

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define  gold_m main
#define Accept return 0;
using namespace std;
typedef long long ll;
const int inf =0x3f3f3f3f;
const int maxn=1e6+5;
const int mod = 1e9+7;
const int N=510;
const long double PI=3.1415926535897932384626433832795;
const long double e=2.71828182845904523536028747135266;
ll mpa[N][N],cnt,head[maxn];
ll dist[N],st[N],n,m;
struct wmy {
    ll u,v,w,next;
} mpa2[maxn];
void add(ll u,ll v,ll w) {
    mpa2[cnt].u=u;
    mpa2[cnt].v=v;
    mpa2[cnt].w=w;
    mpa2[cnt].next=head[u];
    head[u]=cnt++;
}

ll Dijkstra() {
    memset(dist,inf,sizeof(dist));
    dist[1]=0;
    for(int i=1 ; i<=n; i++) {
        int u = -1; // 记录点
        ll min_dist=inf;
        for(int j=1; j<=n; j++) {
            if(st[j]==0&&dist[j]<min_dist) {
                min_dist=dist[j];
                u=j;
            }
        }
        st[u]=1;
        for(int k=1; k<=n; k++)
            dist[k]=min(dist[k],dist[u]+mpa[u][k]);
    }
    if(dist[n]>=inf) return -1;
    else
        return dist[n];
}
ll Dijkstra2() {
    memset(dist,inf,sizeof(dist));
    dist[1]=0;
    for(int i=1 ; i<=n; i++) {
        int u = -1; // 记录点
        ll min_dist=inf;
        for(int j=1; j<=n; j++) {
            if(st[j]==0&&dist[j]<min_dist) {
                min_dist=dist[j];
                u=j;
            }
        }
        st[u]=1;
        for(int j=head[u]; j!=-1; j=mpa2[j].next) {
            if(dist[mpa2[j].v]>dist[u]+mpa2[j].w)
                dist[mpa2[j].v]=dist[u]+mpa2[j].w;
            }

    }
    if(dist[n]>=inf) return -1;
    else
        return dist[n];

}
int   gold_m() {
    cin>>n>>m;
    memset(mpa,inf,sizeof(mpa));
    memset(mpa2,inf,sizeof(mpa2));
    memset(head,-1,sizeof(head));
    /*  while(m--) {
            ll x,y,z;
            cin>>x>>y>>z;
            mpa[x][y]=min(z,mpa[x][y]);
        }*/

    while(m--) {
        ll x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }

    cout<<Dijkstra2()<<endl;
    Accept;
}

/*
5 5
1 2 3
3 1 4
2 4 6
4 2 1
1 4 7
*/