#include <fstream>
#include <vector>
#define inf (999999999)
using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
int cst[50003],h[50003],n,m,k;
bool viz[50003];
vector <int> v[50003];
vector <int> co[50003];
void citire ()
{
    int i,a,b,c;
    in>>n>>m;
    cst[1]=0;
    for(i=2;i<=n;++i)
        cst[i]=inf;
    cst[0]=inf;
    for(i=1;i<=m;++i)
    {
        in>>a>>b>>c;
        v[a].push_back(b);
        co[a].push_back(c);
    }
}
void shift_up (int poz)
{
    while(poz>1 && cst[h[poz]]<cst[h[poz/2]])
    {
        swap(h[poz],h[poz/2]);
        poz>>=1;
    }
}
void shift_down (int poz)
{
    while(poz*2<k && cst[h[poz]]>min(cst[h[poz*2]],cst[h[poz*2+1]]))
    {
        if(cst[h[poz*2]]<cst[h[poz*2+1]])
        {
            swap(h[poz],h[poz*2]);
            poz<<=1;
        }
        else
        {
            swap(h[poz],h[poz*2+1]);
            poz<<=1;
            ++poz;
        }
    }
    if(poz*2==k && cst[h[poz]]>cst[h[poz*2]])
        swap(h[poz],h[poz*2]);
}
void dijkstra ()
{
    int nc,nn,i;
    viz[1]=1;
    h[++k]=1;
    while(k)
    {
        nc=h[1];
        swap(h[1],h[k]);
        --k;
        shift_down(1);
   //     viz[nc]=0;
        for(i=0;i<v[nc].size();++i)
        {
            nn=v[nc][i];
            if(cst[nn]>cst[nc]+co[nc][i])
            {
                cst[nn]=cst[nc]+co[nc][i];
                if(!viz[nn])
                {
                    h[++k]=nn;
                    shift_up(k);
                    viz[nn]=1;
                }
            }
        }
    }
}
int main()
{
    citire();
    dijkstra();
    for(int i=2;i<=n;++i)
    {
        if(cst[i]!=inf)
            out<<cst[i]<<' ';
        else
            out<<0<<' ';
    }
    return 0;
}