#include <bits/stdc++.h>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const int MAX = 100000;

class Graph
{
    int NumberOfNodes;
    int NumberOfEdges;
    bool Oriented;
    vector<vector<int>> AdjacencyList;
    vector<pair<int, int>> AdjacencyListWeightedGraph[MAX];

    void DFS(int, bool[]);

    void functionBCC(int, int, int[], int[], stack<int>&, bool[], vector<vector<int>>&);

    void functionSCC(int, int&, int[], int[], stack<int>&, bool[], bool[], vector<vector<int>>&);

    void functionTopologicalSort(int, bool[], vector<int>&);

    void functionCriticalConnections(int, bool[], int[], int[], int[], vector<vector<int>>&);


    public:
        Graph();
        Graph(int, int, bool);
        void Build();
        void BuildFromVector(vector<vector<int>>);
        void BuildWeightedGraph();
        int getNumberOfNodes();
        int getNumberOfEdges();

        void BFS(int, int[]);

        int NumberOfConnectedComponents();

        vector<vector<int>> BiconnectedComponents(int);

        vector<vector<int>> StronglyConnectedComponents();

        vector<int> TopologicalSort();

        //Checks if a graph exists
        bool functionHavelHakimi(vector<int>&);

        vector<vector<int>> CriticalConnections();

        //Prim's Minimum Spanning Tree
        void MinimumSpanningTree(int);

        void Dijkstra(int);

        void BellmanFord(int);
};

//LeetCode Critical Connections Problem
class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections)
    {
        Graph G(n, connections.size(), 0);
        G.BuildFromVector(connections);

        return G.CriticalConnections();
    }
};

int main()
{
    int NumberOfNodes, NumberOfEdges, StartNode;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 1);
    G.BuildWeightedGraph();

    StartNode = 0;
    G.BellmanFord(StartNode);


/*  ----------------------------Dijkstra----------------------------
    int NumberOfNodes, NumberOfEdges, StartNode;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 1);
    G.BuildWeightedGraph();

    StartNode = 0;
    G.Dijkstra(StartNode);
    ----------------------------Dijkstra----------------------------*/



/*  ----------------------------APM----------------------------
    int NumberOfNodes, NumberOfEdges, StartNode;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 0);
    G.BuildWeightedGraph();

    StartNode = 0;
    G.MinimumSpanningTree(StartNode);
    ----------------------------APM----------------------------*/



/*  ----------------------------CCs----------------------------

    Solution S;
    int n = 4;
    vector<vector<int>> connections = {{0,1},{1,2},{2,0},{1,3}}, CCs;

    CCs = S.criticalConnections(n, connections);

    for (unsigned int i = 0; i < CCs.size(); i++)
        cout << "Critical connection " << i + 1 << ": " << CCs[i][0] << " - " << CCs[i][1] << "\n";

    ----------------------------CCs----------------------------*/



/*  ----------------------------HH----------------------------

    Graph G;
    vector<int> Degrees = {5,5,5,3,2,2,2};

    if (G.functionHavelHakimi(Degrees))
        cout << "Yes";
    else
       cout << "No";

    ----------------------------HH----------------------------*/



/*  ----------------------------TS----------------------------

    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 1);
    G.Build();

    vector<int> TopologicalSort = G.TopologicalSort();

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

    for (auto Node : TopologicalSort)
        fout << Node + 1 << " ";

    ----------------------------TS----------------------------*/


/*  ----------------------------SCCs----------------------------

    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 1);
    G.Build();

    vector<vector<int>> SCCs = G.StronglyConnectedComponents();
    fout << SCCs.size() << "\n";

    for (unsigned int i = 0; i < SCCs.size(); i++)
    {
        vector<int> SCC = SCCs[i];

        for (unsigned int j = 0; j < SCC.size(); j++)
        {
            int Node = SCC[j] + 1;
            fout << Node << " ";
        }
        fout << "\n";
    }

    ----------------------------SCCs----------------------------*/


/*  ----------------------------BCCs----------------------------

    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 0);
    G.Build();

    vector<vector<int>> BCCs = G.BiconnectedComponents(0);
    fout << BCCs.size() << "\n";

    for (unsigned int i = 0; i < BCCs.size(); i++)
    {
        vector<int> BCC = BCCs[i];

        for (unsigned int j = 0; j < BCC.size(); j++)
        {
            int node = BCC[j] + 1;
            fout << node << " ";
        }
        fout << "\n";
    }

    ----------------------------BCCs----------------------------*/


/*  ----------------------------DFS----------------------------

    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 0);
    G.Build();

    fout << G.NumberOfConnectedComponents();

    ----------------------------DFS----------------------------*/


/*  ----------------------------BFS----------------------------

    int NumberOfNodes, NumberOfEdges, StartNode;
    fin >> NumberOfNodes >> NumberOfEdges >> StartNode;

    Graph G(NumberOfNodes, NumberOfEdges, true);
    G.Build();

    int Distance[NumberOfNodes];
    StartNode--;
    G.BFS(StartNode, Distance);

    for (int i = 0; i < NumberOfNodes; i++)
        fout << Distance[i] << " ";

    ----------------------------BFS----------------------------*/

    fin.close();
    fout.close();

    return 0;
}

Graph::Graph() : NumberOfNodes(0), NumberOfEdges(0), Oriented(0) { }

Graph::Graph(int _NumberOfNodes, int _NumberOfEdges, bool _Oriented) : NumberOfNodes(_NumberOfNodes), NumberOfEdges(_NumberOfEdges), Oriented(_Oriented)
{
    NumberOfNodes = _NumberOfNodes;
    NumberOfEdges = _NumberOfEdges;
    Oriented = _Oriented;

    for (int i = 0; i < _NumberOfNodes; i++)
        AdjacencyList.push_back( {} );
        //AdjacencyList.push_back(vector<int>());
}

void Graph::Build()
{
    for (int i = 0; i < NumberOfEdges; i++)
    {
        int FirstNode, SecondNode;
        fin >> FirstNode >> SecondNode;
        FirstNode--;
        SecondNode--;

        AdjacencyList[FirstNode].push_back(SecondNode);
        if (!Oriented)
            AdjacencyList[SecondNode].push_back(FirstNode);
    }
}

void Graph::BuildFromVector(vector<vector<int>> Edges)
{
    for(unsigned int i = 0; i < Edges.size(); i++)
    {
        int FirstNode, SecondNode;
        FirstNode = Edges[i][0];
        SecondNode = Edges[i][1];

        AdjacencyList[FirstNode].push_back(SecondNode);
        if (!Oriented)
            AdjacencyList[SecondNode].push_back(FirstNode);

    }
}

void Graph::BuildWeightedGraph()
{
    for (int i = 0; i < NumberOfEdges; i++)
    {
        int FirstNode, SecondNode, Weight;
        fin >> FirstNode >> SecondNode >> Weight;
        FirstNode--;
        SecondNode--;

        AdjacencyListWeightedGraph[FirstNode].push_back(make_pair(SecondNode, Weight));

        if (!Oriented)
            AdjacencyListWeightedGraph[SecondNode].push_back(make_pair(FirstNode, Weight));
    }
}

int Graph::getNumberOfNodes()
{
    return NumberOfNodes;
}

int Graph::getNumberOfEdges()
{
    return NumberOfEdges;
}

void Graph::BFS(int StartNode, int Distance[])
{
    bool Visited[NumberOfNodes];
    queue<int> BFSQueue;

    for(int i = 0; i < NumberOfNodes; i++)
    {
        Visited[i] = 0;
        Distance[i] = -1;
    }

    Visited[StartNode] = 1;
    Distance[StartNode] = 0;
    BFSQueue.push(StartNode);

    while (!BFSQueue.empty())
    {
        int CurrentNode = BFSQueue.front();

        for (unsigned int i = 0; i < AdjacencyList[CurrentNode].size(); i++)
        {
            int AdjacentNode = AdjacencyList[CurrentNode][i];

            if (!Visited[AdjacentNode])
            {
                Visited[AdjacentNode] = 1;
                Distance[AdjacentNode] = Distance[CurrentNode] + 1;
                BFSQueue.push(AdjacentNode);
            }
        }
        BFSQueue.pop();
    }
}

void Graph::DFS(int StartNode, bool Visited[])
{
    Visited[StartNode] = 1;

    for (unsigned int i = 0; i < AdjacencyList[StartNode].size(); i++) //parcurg vecinii nodului
    {
        int NextNode = AdjacencyList[StartNode][i];
        if (!Visited[NextNode])
            DFS(NextNode, Visited);
    }
}

int Graph::NumberOfConnectedComponents()
{
    bool Visited[NumberOfNodes];
    int _NumberOfConnectedComponents = 0;

    for (int i = 0; i < NumberOfNodes; i++)
        Visited[i] = 0;

    for (int i = 0; i < NumberOfNodes; i++)
    {
        if (!Visited[i])
        {
            DFS(i, Visited);
            _NumberOfConnectedComponents++;
        }
    }

    return _NumberOfConnectedComponents;
}

void Graph::functionBCC(int Node, int id, int ids[], int low[], stack<int> &Stack, bool Visited[], vector<vector<int>> &BCCs)
{
    Stack.push(Node);
    Visited[Node] = 1;
    ids[Node] = low[Node] = id++;

    for (unsigned int i = 0; i < AdjacencyList[Node].size(); i++)
    {
        int AdjacentNode = AdjacencyList[Node][i];

        if (Visited[AdjacentNode])
            low[Node] = min(low[Node], ids[AdjacentNode]);
        else
        {
            functionBCC(AdjacentNode, id, ids, low, Stack, Visited, BCCs);

            low[Node] = min(low[Node], low[AdjacentNode]);

            if (low[AdjacentNode] >= ids[Node])
            {
                vector<int> BCC;
                int NodeBCC;

                do {
                    NodeBCC = Stack.top();
                    BCC.push_back(ids[NodeBCC]);
                    Stack.pop();
                    } while (NodeBCC != AdjacentNode);
                BCC.push_back(Node);

                BCCs.push_back(BCC);
            }
        }
    }
}

void Graph::functionSCC(int Node, int &id, int ids[], int low[], stack<int> &Stack, bool onStack[], bool Visited[], vector<vector<int>> &SCCs)
{
    Stack.push(Node);
    onStack[Node] = 1;
    Visited[Node] = 1;
    ids[Node] = low[Node] = id++;

    for (unsigned int i = 0; i < AdjacencyList[Node].size(); i++)
    {
        int AdjacentNode = AdjacencyList[Node][i];

        if (!Visited[AdjacentNode])
        {
            functionSCC(AdjacentNode, id, ids, low, Stack, onStack, Visited, SCCs);

            low[Node] = min(low[Node], low[AdjacentNode]);
        }
        else if (onStack[AdjacentNode])
            low[Node] = min(low[Node], low[AdjacentNode]);
    }

    if (ids[Node] == low[Node])
    {
        vector<int> SCC;
        int NodeSCC;

        do {
            NodeSCC = Stack.top();
            SCC.push_back(NodeSCC);
            Stack.pop();
            onStack[NodeSCC] = 0;
            } while (NodeSCC != Node);

        SCCs.push_back(SCC);
    }
}

vector<vector<int>> Graph::BiconnectedComponents(int Node)
{
    int id = 0, ids[NumberOfNodes], low[NumberOfNodes];
    bool Visited[NumberOfNodes];
    vector<vector<int>> BCCs;
    stack<int> Stack;

    for (int i = 0; i < NumberOfNodes; i++)
        Visited[i] = 0;

    functionBCC(Node, id, ids, low, Stack, Visited, BCCs);

    return BCCs;
}

vector<vector<int>> Graph::StronglyConnectedComponents()
{
    int id = 0, ids[NumberOfNodes], low[NumberOfNodes];
    bool onStack[NumberOfNodes], Visited[NumberOfNodes];
    vector<vector<int>> SCCs;
    stack<int> Stack;

    for (int i = 0; i < NumberOfNodes; i++)
    {
        onStack[i] = 0;
        Visited[i] = 0;
    }

    for (int i = 0; i < NumberOfNodes; i++)
        if (!Visited[i])
            functionSCC(i, id, ids, low, Stack, onStack, Visited, SCCs);

    return SCCs;
}

void Graph::functionTopologicalSort(int StartNode, bool Visited[], vector<int> &TopSort)
{
    Visited[StartNode] = 1;

    for (unsigned int i = 0; i < AdjacencyList[StartNode].size(); i++) //parcurg vecinii nodului
    {
        int NextNode = AdjacencyList[StartNode][i];
        if (!Visited[NextNode])
            functionTopologicalSort(NextNode, Visited, TopSort);
    }
    TopSort.push_back(StartNode);
}


vector<int> Graph::TopologicalSort()
{
    vector<int> TopSort;
    bool Visited[NumberOfNodes];

    for(int i = 0; i < NumberOfNodes; i++)
        Visited[i] = 0;

    for(int i = 0; i < NumberOfNodes; i++)
        if(!Visited[i])
            functionTopologicalSort(i, Visited, TopSort);

    return TopSort;
}

bool Graph::functionHavelHakimi(vector<int> &Degrees) //Checks if a graph exists
{
    NumberOfNodes = Degrees.size();
    sort(Degrees.begin(), Degrees.end(), greater<>());

    if (NumberOfNodes < 1 || Degrees[0] == 0)
        return 1;

    if (accumulate(Degrees.begin(), Degrees.end(), 0) % 2)
        return 0;

    if (Degrees[0] > NumberOfNodes - 1)
        return 0;

    int Element = Degrees[0];
    Degrees.erase(Degrees.begin() + 0);

    for (int i = 0; i < Element; i++)
    {
        if(Degrees[i] > 0)
            Degrees[i]--;
        else
            return 0;
    }

    return functionHavelHakimi(Degrees);
}

void Graph::functionCriticalConnections(int Node, bool Visited[], int disc[], int low[], int parent[], vector<vector<int>> &CCs)
{
    static int time = 0;

    Visited[Node] = 1;
    disc[Node] = low[Node] = ++time;

    for (unsigned int i = 0; i < AdjacencyList[Node].size(); i++)
    {
        int AdjacentNode = AdjacencyList[Node][i];

        if (!Visited[AdjacentNode])
        {
            parent[AdjacentNode] = Node;
            functionCriticalConnections(AdjacentNode, Visited, disc, low, parent, CCs);

            low[Node] = min(low[Node], low[AdjacentNode]);

            if(low[AdjacentNode] > disc[Node])
            {
                vector<int> CC;

                CC.push_back(Node);
                CC.push_back(AdjacentNode);

                CCs.push_back(CC);
            }
        }
        else if (AdjacentNode != parent[Node])
            low[Node] = min (low[Node], disc[AdjacentNode]);
    }
}

vector<vector<int>> Graph::CriticalConnections()
{
    vector<vector<int>> CCs;
    bool Visited[NumberOfNodes];
    int disc[NumberOfNodes], low[NumberOfNodes], parent[NumberOfNodes];

    for (int i = 0; i < NumberOfNodes; i++)
    {
        parent[i] = -1;
        Visited[i] = 0;
    }

    for (int i = 0; i < NumberOfNodes; i++)
        if (!Visited[i])
            functionCriticalConnections(i, Visited, disc, low, parent, CCs);

    return CCs;
}

void Graph::MinimumSpanningTree(int StartNode)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    int totalCost = 0, MinimumSpanningTreeEdges = 0;
    vector<int> key(NumberOfNodes, INF);
    vector<int> parent(NumberOfNodes, -1);
    vector<bool> inMST(NumberOfNodes, 0);

    minHeap.push(make_pair(0, StartNode));
    key[StartNode] = 0;

    while(!minHeap.empty())
    {
        int Node = minHeap.top().second;
        minHeap.pop();

        if(!inMST[Node])
        {
            inMST[Node] = 1;

            for (auto i : AdjacencyListWeightedGraph[Node])
            {
                int AdjacentNode = i.first;
                int Weight = i.second;

                if (!inMST[AdjacentNode] && Weight < key[AdjacentNode])
                {
                    if (key[AdjacentNode] != INF)
                        totalCost -= key[AdjacentNode];
                    else
                        MinimumSpanningTreeEdges++;

                    key[AdjacentNode] = Weight;
                    parent[AdjacentNode] = Node;
                    minHeap.push(make_pair(key[AdjacentNode], AdjacentNode));

                    totalCost += key[AdjacentNode];
                }
            }
        }
    }

    fout << totalCost << "\n" << MinimumSpanningTreeEdges << "\n";

    for (int i = 1; i < NumberOfNodes; i++)
        fout << parent[i] + 1 << " " << i + 1 << "\n";
}

void Graph::Dijkstra(int StartNode)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    vector<int> key(NumberOfNodes, INF);
    vector<bool> inDijkstra(NumberOfNodes, 0);

    minHeap.push(make_pair(0, StartNode));
    key[StartNode] = 0;

    while(!minHeap.empty())
    {
        int Node = minHeap.top().second;
        minHeap.pop();

        if(!inDijkstra[Node])
        {
            inDijkstra[Node] = 1;

            for (auto i : AdjacencyListWeightedGraph[Node])
            {
                int AdjacentNode = i.first;
                int AdjacentNodeWeight = i.second;

                if (key[Node] + AdjacentNodeWeight < key[AdjacentNode])
                {
                    key[AdjacentNode] = key[Node] + AdjacentNodeWeight;
                    minHeap.push(make_pair(key[AdjacentNode], AdjacentNode));
                }
            }
        }
    }

    for (int i = 0; i < NumberOfNodes; i++)
    {
        if (i != StartNode)
        {
            if (key[i] == INF)
            {
                key[i] = 0;
            }
            fout << key[i] << " ";
        }
    }
}

void Graph::BellmanFord(int StartNode)
{
    vector<int> key(NumberOfNodes, INF);
    queue<int> BF;
    bool negativeCycle = 0;

    key[StartNode] = 0;
    BF.push(StartNode);

    while (!BF.empty())
    {
        int Node = BF.front();
        BF.pop();

        for (auto i : AdjacencyListWeightedGraph[Node])
        {
            int AdjacentNode = i.first;
            int AdjacentNodeWeight = i.second;

            if (key[Node] + AdjacentNodeWeight < key[AdjacentNode])
            {
                key[AdjacentNode] = key[Node] + AdjacentNodeWeight;
                BF.push(AdjacentNode);
            }
        }
    }

    BF.push(StartNode);

    while (!BF.empty() && !negativeCycle)
    {
        int Node = BF.front();
        BF.pop();

        for (auto i : AdjacencyListWeightedGraph[Node])
        {
            int AdjacentNode = i.first;
            int AdjacentNodeWeight = i.second;

            if (key[Node] + AdjacentNodeWeight < key[AdjacentNode])
            {
                negativeCycle = 1;
                break;
            }
        }
    }

    if (negativeCycle)
        fout << "Ciclu negativ!";
    else
        for (int i = 0; i < NumberOfNodes; i++)
            if (i != StartNode)
            {
                if (key[i] == INF)
                    key[i] = 0;
                fout << key[i] << " ";
            }
}