#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#define infinit 1000000000

using namespace std;

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

struct nod
{
    int inf,val;
    nod *urm;
};

int d[50010];
bool s[50010];

struct comp
{
    bool operator()(const int v1,const int v2)
    {
        return d[v1]>d[v2];
    }
};

int n,m;
nod *l[50010];
priority_queue <int, vector<int>, comp> q;

void citire()
{
    nod *p;
    int x,y,z;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        p=new nod;
        p->inf=y;
        p->val=z;
        p->urm=l[x];
        l[x]=p;
    }
}

void rezolv()
{
    s[1]=0;
    d[1]=0;
    int k,c;
    for(int i=1;i<=n;i++)
    {
        if(i!=1)
            d[i]=infinit;
    }
    q.push(1);
    while(!q.empty())
    {
        k=q.top();
        while(s[k]==1&&!q.empty())
        {
            q.pop();
            k=q.top();
        }
        if(!q.empty())
        {
            s[k]=1;
            for(nod *p=l[k];p;p=p->urm)
            {
                if(s[p->inf]==0)
                    if(d[k]+p->val<d[p->inf])
                    {
                        d[p->inf]=d[k]+p->val;
                        q.push(p->inf);
                    }
            }
            q.pop();
        }
    }
}

void afisare()
{
    for(int i=2;i<=n;i++)
    {
        if(d[i]==infinit)
            d[i]=0;
        fout<<d[i]<<" ";
    }
}

int main()
{
    memset(l,0,sizeof(l));
    citire();
    rezolv();
    afisare();
    return 0;
}