#include <cstdio>
#include <queue>
using namespace std;
struct nod
{
    unsigned short i,j,cost;
    nod *p1;
}*p,*p1,*p2,*p0;
int ct[50005],k,i,m,x,j,ct1,point[50005];
pair<unsigned short,unsigned short>*f[50005];
queue<int>q;
bool g[50005];
const int inf=(1e7)*2;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&x,&m);
    for(k=1,p1=new nod,p0=p1;k<=m;k++)
    {
        scanf("%d%d%d",&i,&j,&ct1);
        p=p1;
        p->i=i;
        p->j=j;
        p->cost=ct1;
        p1=new nod;
        p->p1=p1;
        ct[i]++;
    }
    p->p1=NULL;
    for(k=1;k<=x;k++)
        f[k]=new pair<unsigned short,unsigned short>[ct[k]+1];
    for(k=1,p=p0;k<=m;k++)
    {
        f[p->i][point[p->i]].first=p->j;
        f[p->i][point[p->i]].second=p->cost;
        point[p->i]++;
        p1=p;
        p=p->p1;
        delete p1;
    }
    for(k=1;k<=x;k++)
        point[k]=inf;
    for(q.push(1),g[1]=1,point[1]=0;!q.empty();)
    {
        k=q.front();
        q.pop();
        g[k]=0;
        for(i=0;i<ct[k];i++)
        {
            if(point[f[k][i].first]>point[k]+f[k][i].second)
            {
                point[f[k][i].first]=point[k]+f[k][i].second;
                if(!g[f[k][i].first])
                {
                    q.push(f[k][i].first);
                    g[f[k][i].first]=1;
                }
            }
        }
    }
    for(k=2;k<=x;k++)
    {
        if(point[k]==inf)
            printf("0 ");
        else
            printf("%d ",point[k]);
    }
    printf("\n");
    return 0;
}