#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int, int>> v[50001];

int d[50001];

bool viz[50001];

int n,m;

void Dijkstra (int x)
{
    for(int i=1;i<=n;i++)
        d[i]=1000000001;
    set<pair<int, int>> a;
    d[x]=0;
    a.insert({0,x});
    while(!a.empty()){
        int nod;
        nod=a.begin()->second;
        a.erase(a.begin());
        if(!viz[nod]){
            viz[nod]=true;
            for(auto& i:v[nod]){
                int y,c;
                y=i.first;
                c=i.second;
                if(d[nod]+c<d[y]){
                    d[y]=d[nod]+c;
                    a.insert({d[y],y});
                }
            }
        }
    }
}

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        in>>x>>y>>c;
        v[x].push_back({y,c});
    }
    Dijkstra(1);
    for(int i=2;i<=n;i++)
        if(d[i]!=1000000001)
            out<<d[i]<<' ';
        else
            out<<0<<' ';
    return 0;
}