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

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

int n, m, i, j, x, y, c, k, d[50100], v[50100], minim, nod2, cost, nod;
vector< pair<int,int> >a[50100];
const int inf=(1<<30);

int main(){
    fin>>n>>m;
    for (i=1; i<=m; i++){
        fin>>x>>y>>c;
        a[x].push_back(make_pair(y, c));
    }
    for(i=2; i<=n; i++){
        d[i]=inf;
    }
    for(k=1; k<=n; k++){
        minim=inf;
        for(i=1; i<=n; i++){
            if(d[i]<minim && v[i]==0){
                minim=d[i];
                nod=i;
            }
        }
        v[nod]=1;
        for(i=0; i<a[nod].size(); i++){
            nod2=a[nod][i].first;
            cost=a[nod][i].second;
            if(d[nod]+cost<d[nod2]){
                d[nod2]=d[nod]+cost;
            }
        }
    }
    for(i=2; i<=n; i++){
        fout<<d[i]<<" ";
    }
}