#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;

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

struct muchie
{
    int nod, cost;
    bool operator <(const muchie &A) const
    {
        return cost>A.cost;
    }
};
int n,m;
vector<muchie> v[50005];
priority_queue<muchie> q;
bool ap[50005];
int dist[50005];

void Citire()
{
    fin>>n>>m;
    muchie aux;
    for(int i=1; i<=m; i++)
    {
        int A;
        fin>>A>>aux.nod>>aux.cost;
        v[A].push_back(aux);
    }
}

void Dijkstra()
{
    for(int i=1; i<=n; i++)
        dist[i]=INF;
    dist[1]=0;
    muchie aux;
    aux.nod=1;
    aux.cost=0;
    q.push(aux);
    while(!q.empty())
    {
        aux=q.top();
        q.pop();
        int nod=aux.nod;
        if(!ap[nod])
        {
            ap[nod]=1;
            for(auto x: v[nod])
            {
                if(dist[nod]+x.cost<dist[x.nod])
                {
                    dist[x.nod]=dist[nod]+x.cost;
                    aux.nod=x.nod;
                    aux.cost=dist[x.nod];
                    q.push(aux);
                }
            }
        }

    }
}

void Afisare()
{
    for(int i=2; i<=n; i++)
    {
        if(dist[i]==INF)
            fout<<"0 ";
        else
            fout<<dist[i]<<" ";
    }
}

int main()
{
    Citire();
    Dijkstra();
    Afisare();
    return 0;
}