#include <bits/stdc++.h>
#include <queue>
#include <vector>
#define INF 200000047

using namespace std;

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


int viz[50001], d[50001];

struct ura
{
    int nodulet,c;
};

vector <ura> lista[50001];

struct cmp
{
    bool operator()(const ura &a, const ura &b)
    {
        return a.c>b.c;
    }
};

priority_queue <ura,vector<ura>,cmp> prior_que;

void dj(int nod)
{
    d[nod]=0;
    prior_que.push({nod,0});
    while(!prior_que.empty())
    {
        ura aux;
        aux=prior_que.top();
        prior_que.pop();
        if(viz[aux.nodulet]==0){
            viz[aux.nodulet]=1;
           for (auto next : lista[aux.nodulet]){
                if(d[next.nodulet]>d[aux.nodulet]+next.c)

                {
                    d[next.nodulet]=d[aux.nodulet]+next.c;
                    prior_que.push({next.nodulet,d[aux.nodulet]+next.c});
                }
           }
        }
    }
}
int main()
{

    int n,m,i,j,A,B,C;
    in>>n>>m;

    for(i=1;i<=n;++i)
        d[i]=INF;
    for(i=1;i<=m;++i)
    {
        in>>A>>B>>C;
        lista[A].push_back({B,C});
    }
    dj(1);
    for(i=2;i<=n;++i)
        if(d[i]==INF)
            out<<"0 ";
        else
            out<<d[i]<<" ";
    return 0;
}