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

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

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;
    vector<pair<pair<int, int>, int> > edges;
    vector<pair<pair<int, int>, int> > :: iterator it;

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

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

    for (i = 1; i < n; ++i)
    {
        for (it = edges.begin(); it != edges.end(); ++it)
        {
            d = l[(it->first).first] + it->second;
            if (d < l[(it->first).second])
            {
                l[(it->first).second] = d;
            }
        }
    }

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