#include <iostream>
#include <fstream>
#include <bitset>
#include <cstring>
#include <vector>
#include <set>
#define N 50005
#define c first
#define nd second
#define inf 100000005
#define mp make_pair
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector<pair<int,int> > v[N];
bitset<N> b;
set<pair<int,int> > s;
int n, m;
long long d[N];

void dijkstra(){
    for(int i=1; i<=n; i++)d[i]=inf;
    d[1]=0;
    int mn, node;
    s.insert(mp(0, 1));
    while(s.size()>0){
        node=s.begin()->nd;
        s.erase(s.begin());
        b[node]=1;
        for(int j=0; j<v[node].size(); j++){
            if(!b[v[node][j].nd]&&d[v[node][j].nd]>d[node]+v[node][j].c){
                if(d[v[node][j].nd]!=inf)s.erase(s.find(mp(d[v[node][j].nd], v[node][j].nd)));
                d[v[node][j].nd]=d[node]+v[node][j].c;
                s.insert(mp(d[v[node][j].nd], v[node][j].nd));
            }
        }
    }
}

int main(){
    in>>n>>m;
    int x, y, z;
    for(int i=1; i<=m; i++){
        in>>x>>y>>z;
        v[x].push_back(mp(z, y));
    }
    dijkstra();
    for(int i=2; i<=n; i++){
        if(d[i]==inf)out<<0<<" ";
        else out<<d[i]<<" ";
    }
    return 0;
}