#include <stdio.h>
#define MAX 50001
#define MAX2 250001

long n, m;
struct muchie{
    int v1, v2;
    int cost;
};

long d[MAX];
muchie a[MAX2];

void citire();
void Bellman();


int main()
{
    citire();
    Bellman();
    return 0;
}

void citire()
{
    FILE *in = fopen("dijkstra.in","rt");
    fscanf(in,"%ld %ld",&n,&m);
    for (int i = 1; i<=m; i++)
    {
        fscanf(in,"%d",&a[i].v1);
        fscanf(in,"%d",&a[i].v2);
        fscanf(in,"%d",&a[i].cost);
        if (a[i].v1 == 1) d[a[i].v2] = a[i].cost;
    }
    fclose(in);
    for (int i = 1; i<= n; i++)
    {
        if (d[i] == 0) d[i] = MAX;
    }
    d[1] = 0;
}

void Bellman()
{
    int ok = 1;
    while (ok)
    {
        ok = 0;
        for (int i = 1; i<=m; i++)
        {
            if(d[a[i].v2]>d[a[i].v1]+a[i].cost)
			      {
               d[a[i].v2]=d[a[i].v1]+a[i].cost;
	             ok = 1;
            }
        }
    }
    FILE *out = fopen("dijkstra.out","wt");
    for (int i = 2; i<= n; i++)
     fprintf(out,"%ld ", d[i]==MAX ? 0 : d[i]);
    fclose(out);
    
}