#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50004
#define INF 50000004

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, p=1;
int nr[NMAX];

struct varf {
    int x;
    int cost;
};

vector <varf> G[NMAX];
bool uz[NMAX];
int cmin[NMAX];
int pre[NMAX];
queue <int> C;

void citire();
bool bellmanford();
void afisare();

int main()
{
 citire();
 if (!bellmanford()) {
    fout<<"Ciclu negativ!\n";
 } else afisare();
 return 0;
}

void citire() {
    int x, y, cost;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>y>>cost;
        G[x].push_back({y, cost});
    }

}

bool bellmanford() {
   for (int i=1; i<=n; i++) cmin[i] = INF;
   cmin[p] = 0;
   int x;
   C.push(p); nr[p] = 1;
   while (!C.empty()) {
        x = C.front(); C.pop();
        for (int i=0; i<G[x].size(); i++) {
            if (cmin[G[x][i].x] > cmin[x]+G[x][i].cost) {
                cmin[G[x][i].x] = cmin[x]+G[x][i].cost;
                C.push(G[x][i].x);
                nr[G[x][i].x]++;
                if (nr[G[x][i].x] == n) return 0;
            }
        }
   }
   return 1;
}


void afisare() {
    for (int i=2; i<=n; i++) {
        fout<<cmin[i]<<' ';

    }
    fout<<'\n';
}