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

queue<int> c;
vector<arc> g[50005];
long i,j,n,m,x,d[50005];
bool incoada[50005];
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);
    incoada[1]=true;
    while(c.size())
    {
        x=c.front();
        incoada[x]=false;
        c.pop();
        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;
                if(incoada[g[x][i].y]==false)
                {
                    c.push(g[x][i].y);
                    incoada[g[x][i].y]=true;
                }
            }
    }
    for(i=2;i<=n;i++)
        fprintf(f2,"%ld ",d[i]);
    return 0;
}