#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
typedef long long ll;
int N,M;
vector <pair <int,int> > V[50010];
ll rs[50010];


void dijkstra(int x){
    set <pair <int,int> > S;
    S.insert(make_pair(0,1));
    rs[x]=0;
    while (!S.empty()){
        int sr=S.begin()->second;
        S.erase(S.begin());
        for (auto it:V[sr]){
            int weight=it.second;
            int vert=it.first;
            if (rs[sr]+weight<rs[vert]){
                if (rs[vert]!=1e9) S.erase(S.find(make_pair(rs[vert],vert)));
                rs[vert]=rs[sr]+weight;
                S.insert(make_pair(rs[vert],vert));

            }



        }


    }
    for (int i=2;i<=N;i++) fout <<(rs[i]==1e9?0:rs[i])<<" ";


}

int main()
{
    fin >>N>>M;
    for (int a,b,c;M--;){
        fin >>a>>b>>c;
    //    cout <<M;
        V[a].push_back(make_pair(b,c));


    }
    for (int i=1;i<=N;i++) rs[i]=1e9;
    dijkstra(1);
    return 0;
}