dijkstra

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

#define si(a) scanf("%d",&a)
#define f first
#define s second
#define mp(a,b) make_pair(a,b)
#define MAX 1005

int dist[MAX];
vector<pair<int,int> > graph[MAX];

void dijkstra(int st)
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
    Q.push(mp(0,st));
    memset(dist,-1,sizeof(dist));
    while(!Q.empty()){

        int u=Q.top().s,ds=Q.top().f;
        Q.pop();

        if(dist[u]!=-1)
            continue;
        dist[u]=ds;
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i].f,w=graph[u][i].s;
            Q.push(mp(ds+w,v));
        }
    }
    return ;
}

int main()
{
    //freopen("input","r",stdin);
    int n,m,i;
    si(n);si(m);
    for(i=0;i<m;i++){
        int u,v,w;
        si(u);si(v);si(w);
        u--;v--;
        graph[u].push_back(mp(v,w));
        graph[v].push_back(mp(u,w));
    }
    dijkstra(0);
    for(i=0;i<n;i++)
        cout<<dist[i]<<" ";
    cout<<endl;
    return 0;
}


// priority_queue<int,vector<int>,greater<int> > less_val_first;
// priority_queue<int> greater_val_first;