#include <cstdio>
#include <algorithm>
#include <vector>
#define LIM 50023
using namespace std;
struct heap
{
    int nod;
    int val;
}a[LIM];
vector<int>adj[LIM],cst[LIM];
int unde[LIM],nt,n,m,minim[LIM];
int stanga(int x)
{
    return 2*x;
}
int dreapta(int x)
{
    return 2*x+1;
}
int tata(int x)
{
    return x/2;
}
void checkup(int pos)
{
    while(1)
    {
        int t=tata(pos);
        if(t==0) return;
        if(a[t].val>a[pos].val)
        {
            swap(a[t].nod,a[pos].nod);
            swap(a[t].val,a[pos].val);
            swap(unde[a[t].nod],unde[a[pos].nod]);
            pos=t;
        }
        else return;
    }
}
void checkdown(int pos)
{
    while(1)
    {
        int mini=a[pos].val,caz=0;
        int s=stanga(pos);
        if(s<=nt&&mini>a[s].val)
        {
            mini=a[s].val;
            caz=1;
        }
        int dr=dreapta(pos);
        if(dr<=nt&&mini>a[dr].val)
        {
            mini=a[dr].val;
            caz=2;
        }
        if(caz==0) break;
        else if(caz==1)
        {
            swap(a[s].nod,a[pos].nod);
            swap(a[s].val,a[pos].val);
            swap(unde[a[s].nod],unde[a[pos].nod]);
            pos=s;
        }
        else
        {
            swap(a[dr].nod,a[pos].nod);
            swap(a[dr].val,a[pos].val);
            swap(unde[a[dr].nod],unde[a[pos].nod]);
            pos=dr;
        }
    }
}
void rem()
{
    swap(a[1].nod,a[nt].nod);
    swap(a[1].val,a[nt].val);
    swap(unde[a[1].nod],unde[a[nt].nod]);
    nt--;
    checkdown(1);
}

int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) minim[i]=1000000000;
    int a1,a2,a3;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a1,&a2,&a3);
        adj[a1].push_back(a2);
        cst[a1].push_back(a3);
    }
    minim[1]=0;
    for(int i=1;i<=n;i++)
    {
        nt++;
        a[i].nod=i;
        a[i].val=minim[i];
        unde[i]=i;
        checkup(i);
    }
    for(int i=1;i<n;i++)
    {
        int cur=a[1].nod;
        vector<int>::iterator it1,it2;
        it2=cst[cur].begin();
        for(it1=adj[cur].begin();it1!=adj[cur].end();++it1)
        {
            if(minim[cur]+*it2<minim[*it1])
            {
                minim[*it1]=minim[cur]+*it2;
                a[unde[*it1]].val=minim[*it1];
                checkup(unde[*it1]);
            }
            ++it2;
        }
        rem();
    }
    for(int i=2;i<=n;i++) printf("%d ",minim[i]%1000000000);
}