#include<cstdio>
#include<queue>
#define INF 0x3f3f3f3f
#define Nmx 50001

using namespace std;

int n,m,C[Nmx],viz[Nmx];
char a[Nmx];
queue <int> q;
struct nod
{
    int inf;
    int cost;
    nod *urm;
};
nod *G[Nmx];

void add(int x,int y,int c)
{
    nod *aux=new nod;
    aux->inf=y;
    aux->cost=c;
    aux->urm=G[x];
    G[x]=aux;
}

void citire()
{
    int x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fgets(a,Nmx,stdin);
        int j=0;
        x=y=c=0;
        for (; a[j]>='0' && a[j]<='9'; ++j)
            x=x*10+a[j]-'0';
        for (++j; a[j]>='0' && a[j]<='9'; ++j)
            y=y*10+a[j]-'0';
        for (++j; a[j]>='0' && a[j]<='9'; ++j)
            c=c*10+a[j]-'0';
        add(x,y,c);
    }
}

void solve()
{
    for(int i=1;i<=n;++i)
        C[i]=INF;
    q.push(1);
    C[1]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        viz[x]=0;
        for(nod *p=G[x];p;p=p->urm)
            if(C[x]+p->cost<C[p->inf])
            {
                C[p->inf]=C[x]+p->cost;
                if(!viz[p->inf])
                {
                    q.push(p->inf);
                    viz[p->inf]=1;
                }
            }
    }
}

void afisare()
{
    for(int i=2;i<=n;++i)
        if(C[i]==INF)
            printf("0 ");
        else printf("%d ",C[i]);
    printf("\n");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    solve();
    afisare();
    return 0;
}