#include <cstdio>
#include <vector>
#include <queue>
#define INF 50000001
#define NMAX 500001

using namespace std;

struct muchie
{
    int dest, cost;
    muchie *purm;
} *vpmuchii[NMAX];

int m, n;
long long int vdist1[NMAX];

void add(int i, int dest, int cost)
{
    muchie *np = new muchie;
    np->cost = cost;
    np->dest = dest;
    np->purm = vpmuchii[i];
    vpmuchii[i] = np;
}

void citeste()
{
    int i, p, q, t;
    FILE *f = fopen("dijkstra.in", "r");
    fscanf(f, "%i%i", &n, &m);
    for(i=0; i<m; i++)
    {
        fscanf(f, "%i%i%i", &p, &q, &t);
        add(p, q, t);
    }
}

void dijkstra(int x)
{
    queue<int> q;
    int t=x;

    q.push(t);
    for(int i = 1; i <=n; i++)
        vdist1[i] = INF;
    vdist1[x] = 0;

    do
    {
        muchie *p = vpmuchii[t];

        while(p != NULL)
        {
            if(vdist1[p->dest] > vdist1[t] + p->cost)
            {
                vdist1[p->dest] = vdist1[t] + p->cost;
                q.push(p->dest);
            }
            p = p->purm;
        }

        q.pop();
        t = q.front();

    }while(!q.empty());
}

void afiseaza()
{
    FILE *f = fopen("dijkstra.out", "w");
    for(int i = 2; i <= n; i++)
        if(vdist1[i] != INF)
            fprintf(f, "%lli ", vdist1[i]);
        else
            fprintf(f, "0 ");
    fclose(f);
}

int main()
{
    citeste();
    dijkstra(1);
    afiseaza();
    return 0;
}