#include <cstdio>

#include <bitset>
#include <queue>
#include <vector>

using namespace std;

#define MAXN 50010
#define INF 1 << 30
#define mp make_pair

int nodes, m;
bool negative_cycle = false;
vector< pair<int, int> > G[MAXN];
vector<int> dist(MAXN, INF);

void read()
{
    scanf("%d %d", &nodes, &m);
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        scanf("%d %d %d", &x, &y, &cost);
        G[x].push_back(mp(y, cost));
    }
}

void bellmanford()
{
    queue<int> q;
    bitset<MAXN> in_queue(false);
    vector<int> in_cnt(MAXN, 0);

    dist[1] = 0, q.push(1), in_queue[1].flip();
    while (!q.empty() && !negative_cycle) {
        int x = q.front();
        q.pop();
        vector< pair<int, int> >:: iterator it;
        for (it = G[x].begin(); it != G[x].end(); ++it) {
            if (dist[it->first] > dist[x] + it->second) {
                dist[it->first] = dist[x] + it->second;
                if (!in_queue[it->first]) {
                    if (in_cnt[it->first] > nodes) 
                        negative_cycle = true;
                    else {
                        q.push(it->first);
                        in_queue[it->first] = true;
                        in_cnt[it->first]++;
                    }
                }
            }
        }
    }
}

void print()
{
    for (int i = 2; i <= nodes; ++i)
        printf("%d ", dist[i]);
    printf("\n");
}

int main()
{
    read();
    bellmanford();
    print();

    return 0;
}