#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
using namespace std;

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

vector<int> el[50005],dist[50005];
int coada[50005],st=1,dr=1,n,m,a,b,c,dfin[50005];

int main()
{
    fin>>n>>m;
    for(;m;m--){
        fin>>a>>b>>c;
        el[a].push_back(b);
        dist[a].push_back(c);
    }
    for(int i=2;i<=n;i++)
        dfin[i]=INT_MAX;
    coada[dr]=1;dr++;
    while(st<dr){
        int k=coada[st];
        for(int i=0;i<el[k].size();i++){
            int j=el[k][i];
            if(dfin[j]==INT_MAX){
                coada[dr]=j;dr++;
            }
            if(dfin[j]>dfin[k]+dist[k][i])
                dfin[j]=dfin[k]+dist[k][i];
        }
        st++;
    }
    for(int i=2;i<=n;i++)
        if(dfin[i]==INT_MAX)
            dfin[i]=0;
    for(int i=2;i<=n;i++)
        fout<<dfin[i]<<" ";
    return 0;
}