#include <bits/stdc++.h>
using namespace std;
class prs{
private:
    FILE *fin;
    char *buff;
    int sp;
    char read_ch(){
    ++sp;
    if(sp==4096){
        sp=0;
        fread(buff,1,4096,fin);
    }
    return buff[sp];
    }
public:
    prs(const char *name){
    fin=fopen(name,"r");
    buff=new char[4096]();
    sp=4095;
    }
    prs& operator >> (int &n){
    char c;
    while(!isdigit(c=read_ch()));
    n=c-'0';
    while(isdigit(c=read_ch()))
        n=n*10+c-'0';
    return *this;
    }
};
const int inf = 0x3f3f3f3f;
int n,m;
int a,b,c;
vector <pair<int,int>> adj[50001];
int dist[50001];
int main()
{
    prs fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        fin>>a>>b>>c;
        adj[a].push_back({b,c});
    }
    memset(dist,inf,sizeof(dist));
    dist[1]=0;
    set <pair<int,int>> s;
    s.insert({0,1});
    while(!s.empty()){
        int curr_node=s.begin()->second;
        s.erase(s.begin());
        for(auto x:adj[curr_node]){
            int to=x.first,cost=x.second;
            if(dist[to]>dist[curr_node]+cost){
                if(dist[to]!=inf)
                    s.erase(s.find({dist[to],to}));
                dist[to]=dist[curr_node]+cost;
                s.insert({dist[to],to});
            }
        }
    }
    for(int i=2;i<=n;++i)
        fout<<(dist[i]==inf?0:dist[i])<<" ";
}