#include <bits/stdc++.h>

using namespace std;
vector<pair<int,int> > A[50005];
int n,m, Rasp[50005];
set<pair<int, int> > d;
char M[50005];
int main()
{ ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
fin>>n>>m;
int a,b,c;
for(int i=0; i<m; i++){
    fin>>a>>b>>c;
    A[a].push_back(make_pair(c,b));
}
for(int i=1; i<=n; i++){
    M[i]=0;
    Rasp[i]=1000000000;
}
M[1]=1;
Rasp[1]=0;
for (unsigned int i=0; i<A[1].size(); i++){
    d.insert(A[1][i]);
    Rasp[A[1][i].second]= A[1][i].first;
}

for(int k=2; k<=n; k++){
        int vf = (*(d.begin())).second;
    int dist=(*(d.begin())).first;
    M[vf]=1;
    d.erase(*(d.begin()));

for (unsigned int i=0; i<A[vf].size(); i++){
        int v=A[vf][i].second;
    if (dist+A[vf][i].first<Rasp[v] && M[v]!=1){
        d.erase(make_pair(Rasp[v], v));
    Rasp[v]=dist+A[vf][i].first;
    d.insert(make_pair(Rasp[v], v));
    }
}
}
for(int j=2; j<=n; j++)
    if (Rasp[j]!=1000000000)
    fout << Rasp[j] << " "; else fout << 0 << " ";
    return 0;
}