#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 print();
    void read_g(int );
    void addE(int, int, int);

    pair< vector<int>, vector<int> > Dijkstra(int);
    vector< vector<int> > paths(int, vector<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);
}

void Graph::print(){
    for(int i=0; i<adj.size(); i++){
        out<<i+1<<": ";
        for(auto &j: adj[i])
            out<<'('<<j.first+1<<','<<j.second<<')';
        out<<'\n';
    }
}

pair<vector<int>,vector<int>> Graph::Dijkstra(int src){
    vector<int> dist(adj.size(),INT_MAX), path(adj.size());
    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, path[sto]=mid;
                    Q.push(make_pair(dist[sto],sto));
                }
            }
    }
    for(int i=0; i<adj.size(); i++)
        if(INT_MAX==dist[i])dist[i]=0;
    return make_pair(dist,path);
}

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