#include <bits/stdc++.h>
using namespace std;

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

int n, m, a[5001][5001], d[5001], vf[5001];

void citire(){
    fin >> n >> m;
    for(int i=1; i<=m; i++){
        int nod1, nod2, cost;
        fin >> nod1 >> nod2 >> cost;
        a[nod1][nod2] = cost;
    }
    for(int i=1; i<=n; i++){
        d[i] = INT_MAX;
    }
    d[1] = 0;
    vf[1] = 1;
    for(int i=1; i<=n; i++){
        if(a[1][i]) d[i] = a[1][i];
    }
}

int main(){
    citire();
    for(int ind=1; ind<=n; ind++){
        int dmin = INT_MAX, nod_min = -1;
        for(int i=1; i<=n; i++)
            if(d[i] < dmin && !vf[i] ) dmin = d[i], nod_min = i;
        if(nod_min != -1){
            vf[nod_min] = 1;
            for(int i=1; i<=n; i++){
                    if(a[nod_min][i] && d[nod_min] + a[nod_min][i] < d[i]) d[i] = d[nod_min] + a[nod_min][i];

            }
        }

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