#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <list>
#include <set>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define INF 0x3f3f3f3f
#define mp make_pair

class graph{
    int V;
    list<pair<int,int>>*adjl;

public:
    graph(int);
    void add(int,int,int);
    vector<int> Dijkstra(int);
};

graph::graph(int v):V(v){
    adjl=new list<pair<int,int>>[V];
}

void graph::add(int x, int y, int w){
    adjl[x].push_back(mp(y,w));
    //adjl[y].push_back(mp(x,w));
}

vector<int> graph::Dijkstra(int src){
    vector<int>dist(V,INF);
    set<pair<int,int>>setds;

    dist[src]=0;
    setds.insert(mp(0,src));

    while(!setds.empty()){
        int x=(*setds.begin()).second;
        setds.erase(setds.begin());

        for(auto &it: adjl[x]){;
            int y=it.first,
                w=it.second;

            if(dist[y]>dist[x]+w){
                if(dist[y]!=INF)
                    setds.erase(setds.find(mp(dist[y],y)));

                dist[y]=dist[x]+w;
                setds.insert(mp(dist[y],y));
            }
        }
    }
    return dist;
}

int main(){
    int N, M, x, y, w;
    in>>N>>M; graph g(N);
    for(int i=0; i<M; i++)
        in>>x>>y>>w, g.add(x-1,y-1,w);

    vector<int>v=g.Dijkstra(0);
    for(int i=1; i<N; i++)
        out<<v[i]<<' ';
    return 0;
}