#include <iostream>
#include <utility>
#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <list>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

class Graph{
    vector< list< pair<int, int> > >adj;
public:
    Graph(int );
    void read_g(int );
    void addE(int, int, int);

    vector<int> Dijkstra(int);
};

Graph::Graph(int N){
    adj=vector< list< pair<int, int> > >(N, list< pair<int, int> >());
}

void Graph::addE(int a, int b, int w){
    adj[a].push_back(make_pair(b,w));
}

void Graph::read_g(int M){
    int a, b, w;
    while((M--)&&(in>>a>>b>>w))
        this->addE(a-1,b-1,w);
}

vector<int> Graph::Dijkstra(int src){
    vector<int> dist(adj.size(),INT_MAX);
    priority_queue< pair<int, int> >Q;
    Q.push(make_pair(dist[src]=0,src));
    while(!Q.empty()){
        int mid=Q.top().second,
            dcr=-Q.top().first;
        Q.pop();

        if(dcr>dist[mid])continue;
            else for(auto it: adj[mid]){
                int sto=it.first,
                    len=it.second;

                if(dist[mid]+len<dist[sto]){
                    dist[sto]=dist[mid]+len;
                    Q.push(make_pair(-dist[sto],sto));
                }
            }
    }
    return dist;
}

int N, M;
int main(){
    in>>N>>M;
    Graph G(N);
    G.read_g(M);
    vector<int>d=G.Dijkstra(0);
    for(int i=1; i<N; i++)
        if(INT_MAX==d[i])out<<0<<' ';
            else out<<d[i]<<' ';
    return 0;
}