/**
  * \author Corneliu-Claudiu Prodescu
  * \date 28 Nov 2010
  *
  */

#include <cstdio>
#include <vector>
#include <limits.h>
#include <queue>

const char  file_in[] = "dijkstra.in";
const char file_out[] = "dijkstra.out";

const int BIG_VALUE = INT_MAX / 2;

using namespace std;

int main()
{
    freopen(file_in, "r", stdin);
    freopen(file_out,"w", stdout);
    int n, m, i, x, y, z, d;
    int *l;
    bool *inQ;

    vector<pair<int, int> > *edges;
    vector<pair<int, int> > :: iterator it;
    queue<int> Q;

    (void) scanf("%10d %10d", &n, &m);

    l   = new int[n];
    inQ = new bool[n];
    edges = new vector<pair<int, int> >[n];
    l[0]  = 0;
    inQ[0]= true;
    for (i = 1; i < n; ++i)
    {
        l[i]   = BIG_VALUE;
        inQ[i] = false;
    }

    for (i = 0; i < m; ++i)
    {
        scanf("%10d %10d %10d", &x, &y, &z);
        edges[x-1].push_back(make_pair(y-1, z));
    }

    Q.push(0);
    while (!Q.empty())
    {
        int node  = Q.front();
        Q.pop();
        inQ[node] = false;
        for (it = edges[node].begin(); it != edges[node].end(); ++it)
        {
            d = l[node] + it->second;
            if (d < l[it->first])
            {
                l[it->first] = d;
                if (!inQ[it->first])
                {
                    Q.push(it->first);
                    inQ[it->first] = true;
                }
            }
        }
    }

    for (i = 1; i < n; ++i)
    {
        if (BIG_VALUE == l[i])
            printf("0 ");
        else
            printf("%d ", l[i]);
    }
    printf("\n");
}