#include <iostream>
#include <bits/stdc++.h>


using namespace std;

ifstream fapm("apm.in");
ofstream gapm("apm.out");

ifstream fbf("bellmanford.in");
ofstream gbf("bellmanford.out");


class Graf
{
    int nrNoduri;
    int nrMuchii;

    vector<vector<pair<int,int>>> costs;
    vector<tuple<int,int,int>> edge;


public:

    //void citire_apm();
    Graf(int n, int m, int type);
    void APM();
    int nodCostMin(vector<int> &helper, vector<bool> &inMst);
    void BF();



};

Graf::Graf(int n, int m, int type)
{

    this->nrNoduri = n;
    this->nrMuchii = m;

    if(type == 1)       ///type = 1 -> pt apm
    {
        this->costs.resize(nrNoduri + 1);

        int nod1, nod2, cost;
        pair<int,int> temp;

        for(int i = 0; i < this->nrMuchii; i++)
        {
            fapm>>nod1>>nod2>>cost;

            temp.first = nod2;
            temp.second = cost;

            this->costs[nod1].push_back(temp);
            temp.first = nod1;
            this->costs[nod2].push_back(temp);
        }
    }
    else
    {
        this->edge.resize(nrNoduri + 1);

        int nod1, nod2, cost;
        tuple<int,int,int> temp;

        //cout<<"test1\n";

        for(int i = 0; i < this->nrMuchii; i++)
        {
            fbf>>nod1>>nod2>>cost;
            temp = make_tuple(nod1,nod2,cost);
            edge[i] = temp;
        }

        //cout<<"test2\n";
    }




}

/*void Graf::citire_apm()
{
    costs.resize(nrNoduri + 1);
    int nod1, nod2, cost;
    pair<int,int> temp;

    fapm>>nrNoduri>>nrMuchii;

    for(int i = 0; i < nrMuchii; i++)
    {
        fapm>>nod1>>nod2>>cost;

        temp.first = nod2;
        temp.second = cost;

        costs[nod1].push_back(temp);
        temp.first = nod1;
        costs[nod2].push_back(temp);
    }

}*/



int Graf::nodCostMin(vector<int> &helper, vector<bool> &inMst)
{
    int minimum, indexOfMin;
    minimum  = INT_MAX;

    for(int i = 1; i <= nrNoduri; i++)
        if(inMst[i] == false && helper[i] < minimum)
        {
            minimum = helper[i];
            indexOfMin = i;
        }

    return indexOfMin;
}
void Graf::APM()
{
    vector<int> parent;         //un fel de vector de tati, aici va fi apm-ul
    vector<bool> inMst;         //un fel de visited
    vector<int> helper;         //cele mai mici costuri din nodul curent
    //se updateaza la fiecare pas

    for(int i = 0 ; i <= nrNoduri; i++)
    {
        helper.push_back(INT_MAX);
        inMst.push_back(false);
        parent.push_back(0);
    }


    helper[1] = 0;
    parent[1] = -1;
    for(int i = 1 ; i <= nrNoduri; i++)
    {
        int nextVertex = nodCostMin(helper, inMst);  //gasim urmatorul nod cu muchia de cost minim
        inMst[nextVertex] = true;

        int sz = costs[nextVertex].size();
        for(int j = 0; j < sz; j++)
        {
            int temp1 = costs[nextVertex][j].first;
            int temp2 = costs[nextVertex][j].second;

            if(inMst[temp1] == false && temp2 < helper[temp1])
            {
                parent[temp1] = nextVertex;
                helper[temp1] = temp2;
            }

        }

    }
    int sum = 0;
    for(int  i = 2; i <= nrNoduri; i++)
        sum += helper[i];



    gapm<<sum<<"\n";
    gapm<<nrNoduri - 1<<"\n";
    for(int  i = 2; i <= nrNoduri; i++)
        gapm<<parent[i]<<" "<<i<<"\n";

}

void Graf::BF()
{
    vector<int> distances(nrNoduri + 1, INT_MAX);

    distances[1] = 0;

    for(int  i = 1; i <= nrNoduri - 1; i++)
    {
        for(int j = 0; j < nrMuchii; j++)
        {

            int temp1 = get<0>(edge[j]);
            int temp2 = get<1>(edge[j]);
            int cost = get<2>(edge[j]);

            if(distances[temp1] != INT_MAX && distances[temp1] + cost < distances[temp2])
                distances[temp2] = distances[temp1] + cost;

        }


    }


    for(int i = 0; i < nrMuchii; i++)
    {
        int temp1 = get<0>(edge[i]);
        int temp2 = get<1>(edge[i]);
        int cost = get<2>(edge[i]);

        if(distances[temp1]!= INT_MAX && distances[temp1] + cost < distances[temp2])
        {
            gbf<<"Ciclu negativ!";
            return;
        }


    }

    for(int i = 2; i <= nrNoduri; i++)
        gbf<<distances[i]<<" ";
}


int main()
{
    int n, m;
    fbf>>n>>m;

    //Graf G(n, m, 1);
    //G.APM();
    Graf G(n, m, 2);
    G.BF();


    return 0;
}