#include <stdio.h>
#include <map>
#include <vector>

using namespace std;
#define INF 1000000000

struct node {
    map <int, int> ngb;
};
typedef struct node Node;
vector <Node> noduri;
vector <int> d;

 void resolve () {
     bool change = true;
     bool first = true;
     while (change)
     {
         change = false;
     for (int i = 1; i < noduri.size(); i++)
     {
         for (map<int, int>::iterator it = noduri[i].ngb.begin(); it != noduri[i].ngb.end(); it++) {
            if (it->second + d[i] < d[it->first])
            {
               d[it->first] = it->second + d[i];
               change = true;
            }
         }
       }
     }
 }
 
             

int main () {
    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);

    int n, m, x, y, z;
    scanf ("%d %d", &n, &m);
    noduri.resize(n);
    d.resize(n);
    for (int i = 0; i < m; i++)
    {
        scanf ("%d %d %d", &x, &y, &z);
 
        noduri[x - 1].ngb.insert (pair <int, int> (y - 1, z));
        if (x == 1)
            d[y - 1] = z;
        else
            d[y - 1] = INF;
    }
    resolve();
    for (int i = 1; i < n; i++)
    {
        //if (d[i] == INF)
          //  printf("0 ");
        //else
            printf ("%d ", d[i]);
    }
    return 0;
}