#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");
using namespace std;
typedef struct {//in inceput , sf =sfrasit, ds, distanta de la inceput la sfarsit
    int in, sf, ds;//mai adug e= energia
} muchie;

int n; /* numar de of noduri */
int nm; /* numar de muchii */
muchie vm[1024]; /* vector de muchii */
int d[32]; /* d[i] minimul distantei de la start (s) la nodul  curent (i) */

#define INFINITY 10000
///Algoritmul lui Belman Ford determina toate distantele minime de la nodul de start la toate celelalte noduri
void bellman_ford(int s) {
    int i, j;

    for (i = 1; i <= n; ++i)
        d[i] = INFINITY;

    d[s] =0;

    for (i = 1; i <= n - 1; ++i)///doar pentru a face numarul de pasi in vederea optimizarii
        for (j = 1; j <= nm; ++j)///d[vm[j].in] distanta de la start la j
            if (d[vm[j].in] + vm[j].ds < d[vm[j].sf])
                d[vm[j].sf] = d[vm[j].in] + vm[j].ds;
}
int main()
{
    int i, j;
    int aij,s;//s= nodul de start

f>>n>>nm;s=1;
        for (j = 1; j <=nm; j++)
            f>>vm[j].in >>vm[j].sf>>vm[j].ds ;
    bellman_ford(s);
 for(i=2;i<=n;i++)
        g<<d[i]<<" ";

}