#include<bits/stdc++.h>

using namespace std;

const int inf = (1e9);

const int dim = (1e5);

char buff[dim + 5];

int pos = 0;

int cnt[7505];

void read(int &nr) {
    int semn = 1;
    nr = 0;


    while (!isdigit(buff[pos])) {

        if (buff[pos] == '-') semn = -1;

        pos++;
        if (pos == dim) {
            pos = 0;
            fread(buff, 1, dim, stdin);
        }


    }


    while (isdigit(buff[pos])) {
        nr = nr * 10 + buff[pos] - '0';
        pos++;
        if (pos == dim) {
            pos = 0;
            fread(buff, 1, dim, stdin);
        }
    }

    nr *= semn;

}

bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
    if (a.second.second == b.second.second)
        return make_pair(a.first, a.second.first) < make_pair(b.first, b.second.first);

    return a.second.second < b.second.second;
}


class DSU {
private:
    int m_nodes;
    vector<int> t;
public:
    DSU(int n) {
        m_nodes = n;
        t.resize(n + 5);
        for (int i = 0; i <= n; i++)
            t[i] = -1;
    }

    inline int getRoot(int x) {
        int y = x;
        while (t[y] > 0) y = t[y];

        int root = y;

        y = x;

        while (y != root) {
            int aux = t[y];
            t[y] = root;
            y = aux;
        }

        return root;
    }

    inline void unite(int x, int y) {
        if (t[x] < t[y]) {
            t[x] += t[y];
            t[y] = x;
        } else {
            t[y] += t[x];
            t[x] = y;
        }
    }

};

class Graph {

private:

    int m_nodes;

    vector <vector<pair < int, int>> >
    m_adjList;

    vector <pair<int, pair < int, int>> >
    m_edges;

    vector<bool> m_visited;

    vector<int> t;


    bool m_areLabeled;


    struct tip {
        int nod;
        long long cost;

        bool operator<(const tip &other) const {
            return cost > other.cost;
        }
    };


    void topSort(vector<int> &solution, vector<bool> &seen, int node, int fat) {

        seen[node] = 1;

        for (auto it: m_adjList[node]) {
            if (seen[it.first]) continue;
            if (it.first == fat) continue;

            topSort(solution, seen, it.first, node);
        }

        solution.push_back(node);
    }

    void
    tarjan(vector<bool> &inStack, vector<int> &st, vector<int> &lvl, vector<int> &low, vector <vector<int>> &solution,
           int node, int fat, int &currentLevel) {
        low[node] = lvl[node] = ++currentLevel;
        st.push_back(node);

        inStack[node] = 1;

        for (auto it: m_adjList[node]) {
            if (!lvl[it.first]) {
                tarjan(inStack, st, lvl, low, solution, it.first, node, currentLevel);
                low[node] = min(low[node], low[it.first]);
            } else if (inStack[it.first]) {
                low[node] = min(low[node], low[it.first]);
            }
        }


        if (low[node] == lvl[node]) {
            solution.push_back({});
            int x = -1;

            while (x != node) {
                x = st.back();
                solution.back().push_back(x);
                inStack[x] = 0;
                st.pop_back();
            }
        }

    }

    void bicoDFS(vector<int> &t, vector <vector<int>> &solution, vector<int> &st, vector<bool> &seen, vector<int> &lvl,
                 vector<int> &low, int node, int fat, int currentLevel) {
        st.push_back(node);
        low[node] = lvl[node] = currentLevel;

        seen[node] = 1;


        for (auto it: m_adjList[node]) {
            if (it.first == fat) continue;

            if (seen[it.first]) {
                low[node] = min(low[node], lvl[it.first]);
                continue;
            }

            t[it.first] = node;
            bicoDFS(t, solution, st, seen, lvl, low, it.first, node, currentLevel + 1);

            low[node] = min(low[node], low[it.first]);

            if (low[it.first] >= lvl[node]) {
                solution.push_back({});
                int x = 0;

                do {
                    x = st.back();
                    solution.back().push_back(x);
                    st.pop_back();
                } while (x != it.first);

                solution.back().push_back(node);
                // exit(0);
            }

        }
    }

public:

    Graph(int nodes, bool areLabeled) {
        m_nodes = nodes;
        m_areLabeled = areLabeled;

        m_adjList.resize(nodes + 5);

        t.resize(nodes + 5);

        for (int i = 0; i <= nodes; i++)
            t[i] = -1;
    }


    void addEdge(int from, int to, int cost = 0) {
        m_adjList[from].push_back(make_pair(to, cost));
        m_edges.push_back(make_pair(from, make_pair(to, cost)));
    }

    void resetVisited() {
        m_visited.resize(m_nodes + 5);

        for (int i = 0; i <= m_nodes; i++)
            m_visited[i] = 0;
    }

    vector<long long> dijkstra(int source) {

        priority_queue <tip> q;

        const long long inf = 10000000000LL;


        vector<long long> dp(m_nodes + 5, inf);

        dp[source] = 0;

        q.push({source, 0LL});

        while (!q.empty()) {
            int nod = q.top().nod;
            long long cost = q.top().cost;
            q.pop();

            if (cost > dp[nod]) continue;

            for (auto it: m_adjList[nod]) {
                long long z = cost + 1LL * it.second;
                if (z < dp[it.first]) {
                    dp[it.first] = z;
                    q.push({it.first, dp[it.first]});
                }
            }
        }

        return dp;
    }

    vector<int> bfs(int source) {
        deque<int> q;

        vector<int> distances(m_nodes + 5, -1);

        distances[source] = 0;

        q.push_back(source);


        while (!q.empty()) {
            int current = q.front();

            q.pop_front();

            for (auto it: m_adjList[current]) {
                if (distances[it.first] == -1) {
                    distances[it.first] = 1 + distances[current];
                    q.push_back(it.first);
                }
            }

        }


        return distances;

    }

    void dfs(int node) {
        m_visited[node] = 1;

        for (auto it: m_adjList[node]) {
            if (m_visited[it.first]) continue;
            dfs(it.first);
        }
    }

    int getCC() {

        resetVisited();

        int ans = 0;
        for (int i = 1; i <= m_nodes; i++)
            if (!m_visited[i]) dfs(i), ans++;


        return ans;
    }


    vector <vector<int>> getSCCs() {
        vector <vector<int>> solution;
        vector<int> lvl(m_nodes + 5, 0);
        vector<int> low(m_nodes + 5, 0);
        vector<int> st;
        vector<bool> inStack(m_nodes + 5, 0);
        int currentLevel = 0;

        for (int i = 1; i <= m_nodes; i++)
            if (!lvl[i])
                tarjan(inStack, st, lvl, low, solution, i, 0, currentLevel);

        return solution;
    }


    vector <vector<int>> getBiconected() {
        vector <vector<int>> solution;
        vector<int> lvl(m_nodes + 5, 0);
        vector<int> low(m_nodes + 5, 0);
        vector<int> st;
        vector<bool> seen(m_nodes + 5, 0);
        vector<int> t(m_nodes + 5, 0);

        bicoDFS(t, solution, st, seen, lvl, low, 1, 0, 1);

        return solution;

    }

    vector <pair<int, int>> getCriticalEdges() {
        vector <vector<int>> solution;
        vector<int> lvl(m_nodes + 5, 0);
        vector<int> low(m_nodes + 5, 0);
        vector<int> st;
        vector<bool> seen(m_nodes + 5, 0);
        vector<int> t(m_nodes + 5, 0);

        bicoDFS(t, solution, st, seen, lvl, low, 1, 0, 1);

        vector <pair<int, int>> criticals;
        for (auto it: m_edges) {
            int x = it.first;
            int y = it.second.first;

            if (x == y) continue;

            if (lvl[x] < lvl[y]) continue;

            if (t[x] == y && low[x] > lvl[y])
                criticals.push_back(make_pair(x, y));
        }


        return criticals;
    }


    vector<int> getTopSort() {
        vector<int> solution;
        vector<bool> seen(m_nodes + 5, 0);

        for (int i = 1; i <= m_nodes; i++)
            if (!seen[i])
                topSort(solution, seen, i, 0);

        reverse(solution.begin(), solution.end());

        return solution;
    }

    static bool HavelHakimi(vector<int> degSequence) {
        sort(degSequence.begin(), degSequence.end());
        reverse(degSequence.begin(), degSequence.end());

        int sz = (int) degSequence.size();

        for (int i = 0; i < sz; i++) {
            if (!degSequence[i]) break;
            for (int j = i + 1; j <= i + degSequence[i]; j++) {
                if (!degSequence[j]) return 0;
                if (j >= sz) return 0;

                degSequence[j]--;
            }


            int p = i + 1;
            int q = i + degSequence[i] + 1;

            vector<int> aux;
            while (p < i + degSequence[i] + 1 && q < sz) {
                if (degSequence[p] > degSequence[q])
                    aux.push_back(degSequence[p]), p++;
                else
                    aux.push_back(degSequence[q]), q++;
            }

            while (q < sz) aux.push_back(degSequence[q]), q++;
            while (p < i + degSequence[i] + 1) aux.push_back(degSequence[p]), p++;

            for (int j = i + 1; j < sz; j++)
                degSequence[j] = aux[j - i - 1];

            degSequence[i] = 0;
            //  for(auto it:degSequence)
            //     printf("%d ",it);
            // printf("\n");
        }


        return 1;
    }


    pair<long long, vector<pair < int, int> > > getMST() {
        sort(m_edges.begin(), m_edges.end(), cmp);
        vector <pair<int, int>> sol;

        DSU disjointSet(m_nodes);


        long long cost = 0;

        for (auto it: m_edges) {
            int x = it.first;
            int y = it.second.first;
            int z = it.second.second;

            int rx = disjointSet.getRoot(x);
            int ry = disjointSet.getRoot(y);

            if (rx != ry) {
                cost += 1LL * z;
                disjointSet.unite(rx, ry);
                sol.push_back(make_pair(x, y));
            }
        }


        return make_pair(cost, sol);

    }

    pair<int, vector<long long> > bellmanFord(int source) {
        deque<int> q;

        vector<bool> inQueue(m_nodes + 5, 0);
        vector<int> seen(m_nodes + 5, 0);


        q.push_back(source);
        inQueue[source] = seen[source] = 1;

        vector<long long> dp(m_nodes + 5, 1LL * INT_MAX);

        dp[source] = 0;

        while (!q.empty()) {
            int node = q.front();

            for (auto it: m_adjList[node]) {
                if (dp[it.first] < dp[node] + it.second) continue;

                dp[it.first] = dp[node] + it.second;
                if (!inQueue[it.first]) {
                    q.push_back(it.first);
                    inQueue[it.first] = 1;
                }

                seen[it.first]++;
                if (seen[it.first] == (m_nodes + 1))
                    return make_pair(-1, dp);
            }

            inQueue[node] = 0;
            q.pop_front();
        }

        return make_pair(0, dp);


    }
};


int main() {

    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int n, m, x, y, z;

    scanf("%d%d", &n, &m);

    Graph G(n, 1);

    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);

        G.addEdge(x, y, z);
        // G.addEdge(y,x,z);
    }


    pair<int, vector<long long>> sol = G.bellmanFord(1);

    if (sol.first == -1) {
        printf("Ciclu negativ!\n");
        return 0;
    } else {
        for (int i = 2; i <= n; i++)
            printf("%lld ", sol.second[i]);
        printf("\n");
    }
    return 0;


}