#include <stdio.h>
#include <vector>
#include <queue>
#define inf 10010000
using namespace std;
struct arc
{
    int y,l;
}aux;

queue<int> c;
vector<arc> g[25005];
long i,j,n,m,x,d[25005];

int main()
{
    FILE *f1,*f2;
    f1=fopen("dijkstra.in","r");
    f2=fopen("dijkstra.out","w");
    fscanf(f1,"%ld%ld",&n,&m);
    for(i=0;i<m;i++)
    {
        fscanf(f1,"%ld%ld%ld",&x,&aux.y,&aux.l);
        g[x].push_back(aux);
    }
    for(i=2;i<=n;i++)
        d[i]=inf;
    c.push(1);
    while(c.size())
    {
        x=c.front();
        for(i=0;i<g[x].size();i++)
            if(d[g[x][i].y]>d[x]+g[x][i].l)
            {
                d[g[x][i].y]=d[x]+g[x][i].l;
                c.push(g[x][i].y);
            }
        c.pop();
    }
    for(i=2;i<=n;i++)
        fprintf(f2,"%ld ",d[i]);
    return 0;
}