#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,d[50000]={0},incoada[50000]={0};
int cmax=(1<<30)-1;
struct compara{
    bool operator()(int x,int y){
        return d[x]>d[y];
    }
};
vector< vector<pair<int,int> > > v;
priority_queue<int,vector<int>,compara> q;
void Dijsktra(int nodstart){
    d[nodstart]=0;
    q.push(nodstart);
    incoada[nodstart]=1;
    while(!q.empty()){
        int nodcurent = q.top();
        q.pop();
        incoada[nodcurent]=0;
        for(size_t i=0;i<v[nodcurent].size();i++){
            int vecin=v[nodcurent][i].first;
            int cost=v[nodcurent][i].second;
            if(d[nodcurent]+cost<d[vecin]){
                d[vecin]=d[nodcurent]+cost;
                if(incoada[vecin]==0){
                    incoada[vecin]=1;
                    q.push(vecin);
                }
            }
        }
    }
}
int main(){
    f>>n>>m;
    v=vector<vector<pair<int,int> > > (n+1);
    for(int i=1;i<=n;i++)
        d[i]=cmax;
    for(int x,y,c,i=0;i<m;i++){
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    Dijsktra(1);
    for(int i=2;i<=n;i++)
        if(d[i]!=cmax)
            g<<d[i]<<" ";
        else
            g<<"0 ";
    f.close();
    g.close();
}