#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <set>
#include <algorithm>

#define inf 2e9

using namespace std;
ifstream in ("bellman.in");
ofstream out ("bellman.out");

struct Muchie
{
    int x, y, cost;
};
struct Node
{
    int x, cost;
};
bool operator<(const Node& a, const Node& b)
{
    if (a.cost == b.cost)
        return a.x < b.x;
    return a.cost < b.cost;
}
bool CompareMuchii(const Muchie& a, const Muchie& b)
{
    if (a.cost == b.cost)
    {
        if (a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    }
    return a.cost < b.cost;
}

vector<int> Dijkstra(int start, int n, vector<vector<Node>> &listaVecini)
{
    vector<int> d(n, inf);
    d[start] = 0;

    set<Node> Set;
    Set.emplace(start, 0);

    while (!Set.empty())
    {
        Node nod = *Set.begin();
        Set.erase(Set.begin());

        for (Node v : listaVecini[nod.x])
            if (d[nod.x] + v.cost < d[v.x])
            {
                if (d[v.x] != inf)
                    Set.erase(Set.find(Node(v.x, d[v.x])));

                d[v.x] = d[nod.x] + v.cost;
                Set.emplace(v.x,d[v.x]);
            }
    }
    return d;
}


void _STDFS (int nod, vector<bool> &viz, vector<vector<Node>> &vecini, vector<int> &S)
{
    viz[nod] = 1;
    for (Node v : vecini[nod])
        if (viz[v.x] == 0)
            _STDFS(v.x, viz, vecini, S);
    S.push_back(nod);
}
vector<int> SortareTopologicaDFS(int n, vector<vector<Node>> &vecini)
{
    vector<bool> viz(n, false);
    vector<int> S;

    for (int i = 0; i < n; i++)
        if (viz[i] == 0)
            _STDFS(i, viz, vecini, S);

    for (int i = 0; i < n / 2; i++)
    {
        swap(S[i], S[n - 1 - i]);
    }
    return S;
}
vector<int> DAG(int start, int n, vector<vector<Node>> &listaVecini)
{
    vector<int> d(n, inf);
    vector<int> sortTop = SortareTopologicaDFS(n, listaVecini);
    d[start] = 0;

    for (int nod : sortTop)
        for (Node v : listaVecini[nod])
            if (d[nod] + v.cost < d[v.x])
            {
                d[v.x] = d[nod] + v.cost;
            }
    return d;
}


vector<int> BellmanFord(int start, int n, vector<vector<Node>> &listaVecini)
{
    vector<int> d(n, inf);
    vector<int> cnt(n, 0);
    d[start] = 0;
    cnt[start] = 1;


    queue<int> Q;
    Q.push(start);

    while (!Q.empty())
    {
        int nod = Q.front();
        Q.pop();

        for (Node v : listaVecini[nod])
        {
            if (d[nod] + v.cost < d[v.x])
            {
                d[v.x] = d[nod] + v.cost;
                Q.push(v.x);
                cnt[v.x] = 1;
                out << "Ciclu negativ!\n";
                return {};

            }
        }
    }

    return d;
}
int main()
{
    int n, m; in >> n >> m;
    vector<Muchie> listaMuchii(m);
    vector<vector<Node>> listaVecini(n);

    for (int i = 0; i < m; i++)
    {
        int x, y, cost; in >> x >> y >> cost;
        x--; y--;
        listaMuchii[i] = Muchie(x, y, cost);
        listaVecini[x].emplace_back(y, cost);
        // for directed graphs
        //listaVecini[y].emplace_back(x, cost);
    }

    vector<int> d = BellmanFord(0, n, listaVecini);

    if (d.size() == 0)
        return 0;
    for (int i = 1; i < n; i++)
        out << ((d[i] != inf) ? d[i] : 0) << " ";
    out << "\n";
    return 0;
}