#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define L 50005
#define oo 0x3f3f3f
#define pb push_back

using namespace std;

int Dist[L];

struct cmp
{
    bool operator ()(const int &a, const int &b)const
    {
        return Dist[a] > Dist[b];
    }
};

priority_queue <int , vector <int>, cmp> Q;

vector <int> V[L];
vector <int> C[L];

bool viz [L];

int n, m, a, b, c;

void citire()
{
    scanf ("%d %d ", &n, &m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d %d",&a,&b,&c);
        V[a].pb(b);
        C[a].pb(c);
    }
}

void dijkstra()
{
    int Top, D, nod, dis;

    for (int i=2;i<=n;i++)
        Dist[i]=oo;

    Q.push(1);

    while(!Q.empty())
    {
        Top=Q.top();
        Q.pop();
        viz[Top]=false;
        D=Dist[Top];
        for (int i=0;i<V[Top].size();i++)
        {
            nod=V[Top][i];
            dis=C[Top][i];
            if (D + dis < Dist[nod])
            {
                Dist[nod]=D+dis;
                if (!viz[nod])
                {
                    viz[nod]=true;
                    Q.push(nod);
                }
            }
        }
    }
}

void afisare()
{
    for (int i=2;i<=n;i++)
        printf("%d ",Dist[i]==oo?0:Dist[i]);
}

int main ()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w", stdout);
    citire();
    dijkstra();
    afisare();
    return 0;
}