#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int, int> > vec[50005];
int n, m;
int viz[50005], tata[50005], d[50005];

void dijkstra(){
    for(int i=1; i<=n; i++){
            int mn = 1e9, nod;
        for(int i=1; i<=n; i++)
            if(viz[i] == 0 and d[i] < mn){
                mn = d[i];
                nod = i;
            }
        viz[nod] = 1;

        for(auto x : vec[nod])
            if(d[x.first] > d[nod] + x.second){
                d[x.first] = d[nod] + x.second;
                tata[x.first] = nod;
            }

    }
}

int main(){
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y, z;
        fin>>x>>y>>z;
        vec[x].push_back(make_pair(y, z));

    }

    for(int i=1; i<=n; i++){
        d[i] = 1e9;
    }

    d[1] = 0;
    viz[1] = 1;

    dijkstra();

    for(int i=2; i<=n; i++)
        fout<<d[i]<<' ';
    return 0;
}