#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int N=50010;
const int oo=1000000010;
int n,m,a,b,c,D[N];
vector<pair<int,int>> v[N];
priority_queue<pair<int,int>>Q;
int main()
{
    f>>n>>m;
    for(; m; m--)
    {
        f>>a>>b>>c;
        v[a].push_back({b,c});
    }
    for(int i=1; i<=n; i++)
        D[i]=oo;
    D[1]=0;
    Q.push({0,1});
    for(; Q.size();)
    {
        tie(c,b)=Q.top();
        Q.pop();
        c=-c;
        if(c>D[b])
            continue;
        D[b]=c;
        for(auto it:v[b])
            if(D[it.first]>c+it.second)
            {
                D[it.first]=c+it.second;
                Q.push({-D[it.first],it.first});
            }

    }
    for(int i=2;i<=n;i++)
        g<<((D[i]==oo)?0:D[i])<<' ';
    return 0;
}