#include <fstream>
#include <vector>

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

struct elem
{
    int i,c;
}el,el1,h[200003];

int cost[50003],k,n,m,x,y,c;
bool viz[50003];

vector <elem> G[50003];



void adauga(elem el)
{
    h[++k]=el;
    int poz=k;
    while(h[poz].c<h[poz/2].c&&poz/2>0)
    {
        swap(h[poz],h[poz/2]);
        poz/=2;
    }
}

void elimina()
{
    h[1]=h[k];
    k--;
    int poz=1;
    while(2*poz<=k)
    {
        int fiu;
        if(2*poz+1<=k)
        {
            if(h[2*poz].c<h[2*poz+1].c)
                fiu=2*poz;
            else
                fiu=2*poz+1;
        }
        else
            fiu=2*poz;
        if(h[poz].c<h[fiu].c)
            return;
        else
        {
            swap(h[poz],h[fiu]);
            poz=fiu;
        }
    }
}


void dijkstra()
{
    el.i=1;
    el.c=0;
    adauga(el);
    while(k>0)
    {
        el=h[1];
        elimina();
        if(viz[el.i]==0)
        {
            viz[el.i]=1;
            cost[el.i]=el.c;
            for(vector <elem>::iterator it=G[el.i].begin();it!=G[el.i].end();it++)
            if(viz[it->i]==0&&it->c+el.c<cost[it->i])
            {
                el1.i=it->i;
                el1.c=it->c+el.c;
                adauga(el1);
            }
        }
    }
}



int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        el.i=y;
        el.c=c;
        G[x].push_back(el);
    }
    for(int i=2;i<=n;i++)
        cost[i]=1000000000;
    dijkstra();
    for(int i=2;i<=n;i++)
    if(cost[i]<1000000000)
        fout<<cost[i]<<" ";
    else
        fout<<"0 ";
    return 0;
}