dijkstra

/*
    Task        : Dijkstra
    Author      : Phumipat C. [MAGCARI]
    Language    : C++
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    int v,w;
    bool operator < (const A&o) const{
        return w>o.w;
    }
};
priority_queue<A > heap;
vector<A > g[100010];
int dis[100010];
int main(){
    int n,m,u,v,w;
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int i=1;i<=n;i++)
        dis[i] = 1e9;
    dis[1] = 0;
    heap.push({1,0});
    while(!heap.empty()){
        A now = heap.top();
        heap.pop();
        for(auto x:g[now.v]){
            if(dis[x.v] > now.w + x.w){
                dis[x.v] = now.w + x.w;
                heap. Push({x.v,now.w+x.w});
            }
        }
    }
    printf("%d\n",dis[n]);
    return 0;
}