#include <fstream>
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

#define INF 2147483647

//enum properties { Directed = true, unDirected = false, Weighted = true, unWeighted = false };


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

//ifstream fin("input");
//ofstream fout("output");



class Graph
{
// Implementation of  << UTILITARY Functions >>  for (UN)Directed & (UN)Weighted  << Graphs >>;

#pragma region Data

    int nrNodes;
    int nrEdges;
    bool isDirected;
    bool isWeighted;

    vector<list<pair<int, int>>> adjacencyList;

#pragma endregion


public:

#pragma region IO_Methods

    Graph(int n = 0, int m = 0, bool d = false, bool w = false) : nrNodes(n), nrEdges(m), isDirected(d), isWeighted(w) {}

    void readAdjacencyList()
    {
        adjacencyList.resize(nrNodes + 1);

        if (!isWeighted)
        {
            int x, y;

            if (!isDirected)
            {
                for (int i = 0; i < nrEdges; i++)
                {
                    fin >> x >> y;
                    adjacencyList[x].push_back(make_pair(y, 0));
                    adjacencyList[y].push_back(make_pair(x, 0));
                }
            }
            else
            {
                for (int i = 0; i < nrEdges; i++)
                {
                    fin >> x >> y;
                    adjacencyList[x].push_back(make_pair(y, 0));
                }
            }
        }
        else
        {
            int x, y, c;

            if (!isDirected)
            {
                for (int i = 0; i < nrEdges; i++)
                {
                    fin >> x >> y >> c;
                    adjacencyList[x].push_back(make_pair(y, c));
                    adjacencyList[y].push_back(make_pair(x, c));
                }
            }
            else
            {
                for (int i = 0; i < nrEdges; i++)
                {
                    fin >> x >> y >> c;
                    adjacencyList[x].push_back(make_pair(y, c));
                }
            }
        }
    }

    void printAdjacencyList()
    {
        fout << "\n>   nrNodes = " << nrNodes;
        fout << "\n>   nrEdges = " << nrEdges;

        fout << "\n\n\n>   The ADJACENCY LIST associated to the";
        isDirected ? fout << "DIRECTED" : fout << "UNDIRECTED";
        isWeighted ? fout << ", WEIGHTED" : fout << ", UNWEIGHTED";
        fout << " graph <G>:";

        for (int i = 1; i <= nrNodes; i++)
        {
            if (adjacencyList[i].size())
            {
                if (!isWeighted)
                {
                    fout << "\n\nNode " << i << ":    ";
                    for (auto x : adjacencyList[i])
                        fout << x.first << " ";
                }
                else
                {
                    fout << "\n\nNode " << i << ":\n";
                    for (auto x : adjacencyList[i])
                        fout << "     " << i << " --> (" << x.second << ") --> " << x.first << "\n";
                }
            }
        }
    }

#pragma endregion

#pragma region Unweighted_Graph_Methods

    vector<int> getUnweightedDistances(int startingNode)
    {
        vector<bool> isVisited(nrNodes + 1, false);
        vector<int> distances(nrNodes + 1, -1);

        BFS(startingNode, isVisited, distances);

        return distances;
    }

    list<set<int>> getConnectedComponents()
    {
        list<set<int>> CClist;
        vector<bool> isVisited(nrNodes + 1, false);

        for (int i = 1; i <= nrNodes; i++) // parcurgem nodurile pana gasim unul nevizitat, indicand o noua componenta conexa, si pornim DFS din acel nod
            if (!isVisited[i])
            {
                set<int> connectedComponent;
                DFS(i, isVisited, connectedComponent);

                CClist.push_back(connectedComponent);
            }

        return CClist;
    }

    list<set<int>> getStronglyConnectedComponents()
    {
        list<set<int>> SCClist;

        vector<int> discoveryOrder(nrNodes + 1, 0);
        vector<int> lowestLink(nrNodes + 1, 0);
        vector<bool> onStack(nrNodes + 1, false);
        stack<int> path;

        for (int i = 1; i <= nrNodes; i++)
            if (!discoveryOrder[i])
                TarjanDFS(i, discoveryOrder, lowestLink, path, onStack, SCClist);

        return SCClist;
    }

    list<set<int>> getBiconnectedComponents()
    {
        list<set<int>> BCClist;

        vector<int> levels(nrNodes + 1, 0);
        vector<int> lowestLink(nrNodes + 1, 0);
        stack<int> path;

        BiconnectedDFS(1, 1, levels, lowestLink, path, BCClist);

        return BCClist;
    }

    list<pair<int, int>> getCriticalEdges()
    {
        list<pair<int, int>> CElist;

        vector<int> discoveryOrder(nrNodes + 1, 0);
        vector<int> lowestLink(nrNodes + 1, 0);

        CriticalEdgesDFS(1, 0, discoveryOrder, lowestLink, CElist);

        return CElist;
    }

    list<int> getTopologicalOrder()
    {
        list<int> TOlist;
        vector<bool> isVisited(nrNodes + 1, false);

        for (int i = 1; i <= nrNodes; i++)
            if (!isVisited[i])
                TopologicalOrderDFS(i, isVisited, TOlist);

        return TOlist;
    }

    bool getValidGraph()
    {
        vector<int> degrees;

        int deg;
        while (fin >> deg)
        {
            degrees.push_back(deg);
        }

        while (!degrees.empty())
        {
            sort(degrees.begin(), degrees.end(), greater<>());

            if (degrees[0] == 0)
                return true;

            if (degrees[0] > degrees.size() - 1)
                return false;

            for (int i = 1; i <= degrees[0]; i++)
            {
                degrees[i]--;

                if (degrees[i] < 0)
                    return false;
            }

            degrees.erase(degrees.begin() + 0);
        }
    }

#pragma endregion

#pragma region Weighted_Graph_Methods

    vector<int> getWeightedDistances(int startingNode)
    {
        vector<int> distance(nrNodes + 1, INF);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> inProcessing;

        Dijkstra(startingNode, inProcessing, distance);

        return distance;
    }

    vector<int> getBellmanFordDistances(int startingNode)
    {
        vector<int> distance(nrNodes + 1, INF);

        BellmanFord(startingNode, distance);

        return distance;
    }

#pragma endregion


private:

#pragma region Private_Methods

    void BFS(int startingNode, vector<bool>& isVisited, vector<int>& dist)
    {
        queue<int> inProcessing;

        inProcessing.push(startingNode);
        isVisited[startingNode] = true; // adaugam nodul de plecare in coada; pornim BFS
        dist[startingNode] = 0;

        while (!inProcessing.empty())
        {
            int currentNode = inProcessing.front(); // extragem primul nod din coada si ii parcurgem/adaugam vecinii in coada

            inProcessing.pop();

            for (auto adjNode : adjacencyList[currentNode]) // vecin.first = nodul din lista de adiacenta a nodului curent
                if (!isVisited[adjNode.first])               // adauga toti vecinii nevizitati ai nodului curent in coada
                {
                    inProcessing.push(adjNode.first);
                    isVisited[adjNode.first] = true;
                    dist[adjNode.first] = dist[currentNode] + 1;
                } 
        }

        dist.erase(dist.begin());
    }

    void DFS(int startingNode, vector<bool>& isVisited, set<int>& connectedComponent)
    {
        isVisited[startingNode] = true;
        connectedComponent.insert(startingNode);

        for (auto adjNode : adjacencyList[startingNode]) // vecin.first = nodul din lista de adiacenta a nodului curent
            if (!isVisited[adjNode.first])          // parcurgem componenta conexa de care apartine nodul de pornire
                DFS(adjNode.first, isVisited, connectedComponent);
    }

    void TarjanDFS(int currentNode, vector<int>& discOrder, vector<int>& lowLink, stack<int>& path, vector<bool>& onStack, list<set<int>>& SCClist)
    {
        static int currentID = 1;
        path.push(currentNode);
        onStack[currentNode] = true;
        discOrder[currentNode] = lowLink[currentNode] = currentID++;

        for (auto adjNode : adjacencyList[currentNode]) // vecin.first = nodul din lista de adiacenta a nodului curent
        {
            if (discOrder[adjNode.first]) // daca nodul vecin a fost explorat si se afla pe stiva de ordine, il incadram intr-o componenta conexa;
            {
                if (onStack[adjNode.first])
                    lowLink[currentNode] = min(lowLink[currentNode], discOrder[adjNode.first]);
            }
            else  // daca nodul vecin nu a fost explorat, pornim DFS din el, iar la revenirea din recursie, il incadram intr-o componenta conexa;
            {
                TarjanDFS(adjNode.first, discOrder, lowLink, path, onStack, SCClist);
                lowLink[currentNode] = min(lowLink[currentNode], lowLink[adjNode.first]);
            }
        }

                                                             // daca ID - ul nodului corespunde cu lowLink - value - ul sau, inseamna ca nodul este radacina componentei sale conexe,
        if (lowLink[currentNode] == discOrder[currentNode])  // si putem scoate de pe stiva toate nodurile pana la startingNode, deoarece am terminat de explorat componenta respectiva;
        {
            set<int> connectedComp;
            int last;

            do
            {
                last = path.top();
                path.pop();
                onStack[last] = false;

                connectedComp.insert(last);
            } while (currentNode != last);

            SCClist.push_back(connectedComp);
        }
    }

    void BiconnectedDFS(int currentNode, int currentLevel, vector<int>& level, vector<int>& lowLink, stack<int>& path, list<set<int>>& BCClist)
    {
        path.push(currentNode); // stiva retine parcurgerea DFS a subarborilor grafului
        level[currentNode] = lowLink[currentNode] = currentLevel; // adancimi[x] = nivelul de adancime al nodului X din arborele DFS;     lowLink[x] = adancimea minima la care se poate intoarce nodul X;

        for (auto adjNode : adjacencyList[currentNode])
        {
            if (level[adjNode.first]) // daca nodul vecin a fost explorat
            {
                lowLink[currentNode] = min(lowLink[currentNode], level[adjNode.first]); // adancimea minima a nodului curent S = min (adancimea sa minima curenta; adancimea vecinilor sai)
            }
            else
            {
                BiconnectedDFS(adjNode.first, currentLevel + 1, level, lowLink, path, BCClist);
                lowLink[currentNode] = min(lowLink[currentNode], lowLink[adjNode.first]); // la intoarcerea din recursie, nodurile cu adancimea < adancimea nodului pe care s-a facut recursia
                                                                         // isi minimizeaza adancimea minima lowLink cu a succesorilor;
                if (lowLink[adjNode.first] == level[currentNode])
                {                                          // cand ajungem la succesorul radacinii componentei, eliminam nodurile pana la radacina din stiva, formand o componenta biconexa;
                    set<int> biconnectedCopm;
                    int last;

                    do
                    {
                        last = path.top();
                        path.pop();

                        biconnectedCopm.insert(last);
                    } while (currentNode != last);

                    path.push(currentNode);

                    BCClist.push_back(biconnectedCopm);
                }
            }
        }
    }

    void CriticalEdgesDFS(int startingNode, int previous, vector<int>& discOrder, vector<int>& lowLink, list<pair<int, int>>& CElist)
    {
        static int currentID = 1;
        discOrder[startingNode] = lowLink[startingNode] = currentID++;

        for (auto adjNode : adjacencyList[startingNode])
        {
            if (discOrder[adjNode.first])
            {
                if (adjNode.first != previous)
                    lowLink[startingNode] = min(lowLink[startingNode], discOrder[adjNode.first]);
            }
            else
            {
                CriticalEdgesDFS(adjNode.first, startingNode, discOrder, lowLink, CElist);

                lowLink[startingNode] = min(lowLink[startingNode], lowLink[adjNode.first]);

                if (lowLink[adjNode.first] > discOrder[startingNode])
                    CElist.push_back(make_pair(startingNode, adjNode.first));
            }      
        }
    }

    void TopologicalOrderDFS(int startingNode, vector<bool>& isVisited, list<int>& TOlist)
    {
        isVisited[startingNode] = true;

        for (auto adjNode : adjacencyList[startingNode])
            if (!isVisited[adjNode.first])
                TopologicalOrderDFS(adjNode.first, isVisited, TOlist);

        TOlist.push_front(startingNode);
    }

    void Dijkstra(int startingNode, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& inProcessing, vector<int>& dist)
    {
        dist[startingNode] = 0;
        inProcessing.push(make_pair(0, startingNode));

        while (!inProcessing.empty())
        {
            int nearestNode = inProcessing.top().second;
            int currentDistance = inProcessing.top().first;
            inProcessing.pop();

            if (currentDistance <= dist[nearestNode])
            {
                for (auto adjNode : adjacencyList[nearestNode])
                {
                    int node = adjNode.first;
                    int cost = adjNode.second;

                    if (dist[node] == INF && dist[nearestNode] + cost < dist[node])
                    {
                        dist[node] = dist[nearestNode] + cost;
                        inProcessing.push(make_pair(dist[node], node));
                    }
                }
            }
        }

        for (auto& d : dist)
            d == INF ? d : 0;

        dist.erase(dist.begin(), dist.begin() + 2);
    }

    void BellmanFord(int startingNode, vector<int>& dist)
    {
        queue<int> processingQueue;
        vector<bool> inQueue(nrNodes + 1, false);
        vector<int> countIterations(nrNodes + 1, 0);

        dist[startingNode] = 0;
        processingQueue.push(startingNode);
        inQueue[startingNode] = true;


        while (!processingQueue.empty())
        {
            int currentNode = processingQueue.front();
            processingQueue.pop();
            inQueue[currentNode] = false;

            countIterations[currentNode]++;
            if (countIterations[currentNode] >= nrNodes)
                break;

            for (auto adjNode : adjacencyList[currentNode])
            {
                int node = adjNode.first;
                int cost = adjNode.second;

                if (dist[node] > dist[currentNode] + cost)
                {
                    dist[node] = dist[currentNode] + cost;

                    if (!inQueue[node])
                    {
                        processingQueue.push(node);
                        inQueue[node] = true;
                    }
                }
            }
        }

        dist[0] = 0;
    }

#pragma endregion

};



int main()
{
    int nodes, edges, start;
    fin >> nodes >> edges;

    Graph G(nodes, edges, true, true); // G(nodes, edges, isDirected, isWeighted);

    G.readAdjacencyList();
    //G.printAdjacencyList();


#pragma region Public_Methods_Calls

/* ---> MINIMAL DISTANCES (UNWEIGHTED) <--- */

    /*vector<int> minDistances_UW = G.getUnweightedDistances(s);

    for (auto dist : minDistances_UW)
        fout << dist << " ";*/


/* ---> CONNECTED COMPONENTS <--- */

    /*list<set<int>> CClist = G.getConnectedComponents();

    fout << CClist.size();*/


/* ---> STRONGLY CONNECTED COMPONENTS <--- */

    /*list<set<int>> SCClist = G.getStronglyConnectedComponents();

    fout << SCClist.size() << "\n";

    for (auto SCC : SCClist)
    {
        for (auto node : SCC)
            fout << node << " ";
        fout << "\n";
    }*/


/* ---> BICONNECTED COMPONENTS <--- */

    /*list<set<int>> BCClist = G.getBiconnectedComponents();

    fout << BCClist.size() << "\n";

    for (auto BCC : BCClist)
    {
        for (auto node : BCC)
            fout << node << " ";
        fout << "\n";
    }*/


/* ---> CRITICAL EDGES <--- */

    /*list<pair<int, int>> CElist = G.getCriticalEdges();

    fout << CElist.size() << "\n";

    for (auto edge : CElist)
        fout << "(" << edge.first << " " << edge.second << ")" << "\n";*/


/* ---> TOPOLOGICAL ORDER <--- */

    /*list<int> TOlist = G.getTopologicalOrder();

    for (auto node : TOlist)
        fout << node << " ";*/


/* ---> GRAPHICAL SEQUENCE <-- - */

    /*bool HH = G.getValidGraph();

    HH ? fout << "Yes" : fout << "No";*/


/* ---> MINIMAL DISTANCES (WEIGHTED) <--- */

    /*vector<int> minDistances_W = G.getWeightedDistances(1);

    for (auto dist : minDistances_W)
        fout << dist << " ";*/


/* ---> MINMAL DISTANCES (W/ NEGATIVE COSTS) <--- */

    vector<int> minDistances_NegC = G.getBellmanFordDistances(1);

    if (!minDistances_NegC[0])
        fout << "Ciclu infinit!";
    else
        for (int i = 2; i < nodes; i++)
            fout << minDistances_NegC[i] << " ";

#pragma endregion
}