#include<fstream>
#define usi unsigned short int
#define inf 1000000000L
#define nmax 50010
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int d[nmax],m;
usi n;

struct nod{
    usi x;
    usi cost;
    nod *urm;
};
nod *lista[nmax];

void adaug(usi a,usi b,usi c)
{
    nod *p;
    p=new nod;
    p->x=b;
    p->cost=c;
    p->urm=lista[a];
    lista[a]=p;
}

void dijkstra(usi vf)
{
    int vmin;
    char viz[nmax];
    nod *p;
    usi t[nmax],poz,i,j;
    for(i=1;i<=n;i++)
    {
        d[i]=inf;
        viz[i]=0;
    }
    d[vf]=0;
    t[vf]=0;

    for(i=1;i<=n;i++)
    {
        vmin=inf;
        for(j=1;j<=n;j++)
        {
            if(viz[j]==0 && d[j]<vmin)
            {
                vmin=d[j];
                poz=j;
            }
        }
        if(vmin==inf)
            break;
        viz[poz]=1;
        for(p=lista[poz];p!=NULL;p=p->urm)
        {
            if(d[p->x]>d[poz]+p->cost)
            {
                d[p->x]=d[poz]+p->cost;
                t[p->x]=poz;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(i!=vf)
        {
            if(d[i]==inf)
                g<<"0 ";
            else
                g<<d[i]<<" ";
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        usi x,y,z;
        f>>x>>y>>z;
        adaug(x,y,z);
    }
    dijkstra(1);
    f.close();
    g.close();
    return 0;
}