//
//  main.cpp
//  Dijkstra
//
//  Created by Alex Petrache on 02/11/14.
//  Copyright (c) 2014 Alex Petrache. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define NMAX 50001
#define INF 999999999
using namespace std;

vector<int> G[NMAX], C[NMAX];
set< pair<int, int> > heap;
int n,m;

int dist[NMAX];

void dijkstra(){
    int i;
    for(i=2;i<=n;i++)
        dist[i]=INF;
    
    heap.insert(make_pair(0,1));
    
    int cost,x,l;
    while(!heap.empty()){
        cost=(*heap.begin()).first;
        x=(*heap.begin()).second;
        heap.erase(*heap.begin());
        l=G[x].size();
        for(i=0;i<l;i++){
            if(dist[G[x][i]]>(C[x][i]+cost)){
                dist[G[x][i]]=C[x][i]+cost;
                heap.insert(make_pair(dist[G[x][i]], G[x][i]));
            }
        }
    }
}

int main(int argc, const char * argv[])
{
    int i,a,b,c;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
//    ifstream f("/Users/alexpetrache/Documents/Programare/Xcode/Arhiva Educationala/Dijkstra/Dijkstra/dijkstra.in");
    f>>n>>m;
    for(i=0;i<m;i++){
        f>>a>>b>>c;
        G[a].push_back(b);
        C[a].push_back(c);
    }
    
    dijkstra();
    
    for(i=2;i<=n;i++)
        if(dist[i]==INF)
            g<<0<<" ";
        else
            g<<dist[i]<<" ";
    return 0;
}