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

void dijkstra(){
    memset(d, inf, sizeof(d));
    d[1]=0;
    int mn, node;
    for(int i=1; i<=n; i++){
        mn=inf;
        for(int j=1; j<=n; j++){
            if(!b[j]&&d[j]<mn){
                mn=d[j];
                node=j;
            }
        }
        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){
                d[v[node][j].nd]=d[node]+v[node][j].c;
            }
        }
    }
}

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