dijkstra算法：1数组，2堆优化

// #include<iostream>
// #include<algorithm>
// #include<cstring>
// using namespace std;
// const int N=510;
// int n,m;
// int dist[N];
// int g[N][N];
// int st[N];

// int dijkstra()
// {
//     memset(dist,0x3f,sizeof dist);
//     dist[1]=0;
//     for(int i=0;i<n;i++)//遍历n遍
//     {
//         int t=-1;
//         for(int j=1;j<=n;j++)
//         {
//             if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;//找到一个离原点最近的点，此时该点已经是最短路
//         }    
//             st[t]=true;
//             for(int j=1;j<=n;j++)dist[j]=min(dist[j],dist[t]+g[t][j]);//用该点更新其他点

//     }
//     if(dist[n]==0x3f3f3f3f)return -1;
//     return dist[n];
// }

// int main()
// {
//     cin>>n>>m;
//     memset(g,0x3f,sizeof g);

//     while(m--)
//     {
//         int a,b,c;
//         cin>>a>>b>>c;
//         g[a][b]=c;//a到b的距离是c
//     }
//     int t=dijkstra();
//     cout<<t;
//     return 0;
// }

// #include<iostream>
// #include<algorithm>
// #include<cstring>
// #include<queue>
// using namespace std;
// typedef pair<int,int>PII;
// const int N=100010;
// int n,m;
// int h[N],w[N],e[N],ne[N],idx;//w数组存了a到b的距离c，挂拉链
// int dist[N];
// bool st[N];

// int dijkstra()
// {
//      memset(dist,0x3f,sizeof dist);
//     dist[1]=0;

//     priority_queue<PII,vector<PII>,greater<PII>>heap;//第1个存储距离，第二个存储下标,优先队列，对头距离最小
//     heap.push({0,1});

//     while(heap.size())
//     {
//         auto t=heap.top();
//         heap.pop();

//         int ver=t.second,distance=t.first;

//         if(st[ver])continue;
//         for(int i=h[ver];i!=-1;i=ne[i])
//         {
//             int j=e[i];
//             if(dist[j]>w[i]+distance)
//             {
//                 dist[j]=w[i]+distance;
//                 heap.push({j,dist[j]});
//             }
//         }

//     }
//     if(dist[n]==0x3f3f3f)return -1;
//     return dist[n];


// }

// void add(int a,int b,int c)
// {
//     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
// }

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}