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

using namespace std;

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

vector<int> listAux[100001];
vector<int> tareConexe[100001];
vector <int> v[50005],d[50005];
int nrTC=0;

struct edge{
    int cost,x,y;
};

//functii cmp pt sortare
bool cmp_edge(const edge &a,
              const edge &b)
{
    return (a.cost < b.cost);
}

bool cmp(const pair<int,int> &a,
         const pair<int,int> &b)
{
    return (a.second > b.second);
}



class Graf{
public:
    Graf(){}
    //rezolvari probleme
    void bfs();
    void dfs();
    void sorttop();
    void havelHakimi();
    void ctc_Kosoraju();
    void dijkstra();
    void disjoint();
    void kruskal();
    void bellmanFord();

private:
    //metode auxiliare
    int find(int x);
    void union_(int x, int y);
    void r_dfs(int q);
    void rr_dfs(int q);
    void sorttop_recursie(int q);


private:
    //date
    int m_nrMuchii;
    int m_nrNoduri;
    int m_start;
    int m_viz[100001];
    int m_q[100001];
    vector<int> m_ordtop;
    vector<int> m_grad;
    vector<int> m_stiva;
    set< pair<int,int> > s;
    vector<pair<int,int>> m_nodGrad;
    int m_aux;
    vector<int> m_list[100001];
    vector<int> m_parent, m_rank;
    vector<int> m_distance;

};



int main() {
    Graf graf;
    graf.bellmanFord();
}


void Graf::bfs()
{
    in>>m_nrNoduri>>m_nrMuchii>>m_start;
    for(int i=0;i<m_nrMuchii;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
    }

    for(int i=1;i<=m_nrNoduri;i++)
    {
        m_viz[i]=2000000000;
    }
    m_viz[m_start]=0;
    m_q[1]=m_start;
    int p=1;
    int u=1;
    while(p<=u) //<=
    {
        int r=m_q[p];
        for(int i=0;i<(m_list[r].size());i++)
        {
            int e=m_list[r][i];
            // cout<<e<<' ';

            if(m_viz[r]+1<m_viz[e])
            {
                m_viz[e]=m_viz[r]+1;
                u++;
                m_q[u]=e;


            }
        }
        p++;
    }
    for(int i=1;i<=m_nrNoduri;i++)
    {
        if(m_viz[i]!=2000000000)
            out<<m_viz[i]<<' ';
        else
            out<<"-1 ";
    }
}

void Graf::r_dfs(int q)
{
    m_viz[q]=1;
    for(int i=0;i<m_list[q].size();i++)
    {

        int r=m_list[q][i];

        if(m_viz[r]==0)
        {
            r_dfs(r);
        }


    }
    m_stiva.push_back(q);
}

void Graf::rr_dfs(int q) //recursie dfs pt tare conexe
{
    m_viz[q]=1;
    for(int i=0;i<m_list[q].size();i++)
    {

        int r=m_list[q][i];

        if(m_viz[r]==0)
        {
            rr_dfs(r);
        }


    }
    tareConexe[nrTC].push_back(q);
}

void Graf::dfs()
{
    in>>m_nrNoduri>>m_nrMuchii;
    for(int i=0;i<m_nrMuchii;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
        m_list[y].push_back(x);
    }

    int s=0;
    for(int i=1;i<=m_nrNoduri;i++)
    {
        if(m_viz[i]==0)
        {
            r_dfs(i);
            s++;
        }
    }
    r_dfs(1);
    out<<s<<'\n';
}

void Graf::sorttop_recursie(int q)
{
    int i;
    m_viz[q]=1;

    for(i=0;i<m_list[q].size();i++)
    {
        int t=m_list[q][i];
        if(m_viz[t]==0)
        {
            sorttop_recursie(t);

        }

    }
    m_aux++;
    m_ordtop[m_aux]=q;
}

void Graf::sorttop()
{
    int i;
    in>>m_nrNoduri>>m_nrMuchii;
    for(i=0;i<m_nrNoduri;i++)
    {
        m_grad.push_back(0);
        m_ordtop.push_back(0);
    }
    for(i=1;i<=m_nrMuchii;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
        m_grad[y]++;
    }
    for(i=1;i<=m_nrNoduri;i++)
    {
        if(m_grad[i]==0 && m_viz[i]==0)
        {
            sorttop_recursie(i);
        }
    }
    //cout<<w<<'\n';
    for(i=m_aux;i>0;i--)
    {
        out<<m_ordtop[i]<<' ';
    }
}

void Graf::havelHakimi()
{
    int s=0;
    in>>m_nrNoduri;
    for(int i=1;i<=m_nrNoduri;i++)
    {
        int x;
        in>>x;
        s+=x;
        m_nodGrad.push_back(make_pair(i,x));
        sort(m_nodGrad.begin(), m_nodGrad.end(),cmp);
    }

    if(s%2==0)
    {
        for(int i=1;i<=m_nrNoduri;i++)
        {
            if(m_nodGrad[i-1].second <= m_nrNoduri - i)
            {
                int aux = m_nodGrad[i-1].second;
                for(int j = 1; j <= aux; j++)
                {
                    m_nodGrad[i+j-1].second--;
                    m_nodGrad[i-1].second--;
                    m_list[m_nodGrad[i-1].first].push_back(m_nodGrad[i+j-1].first);
                    m_list[m_nodGrad[i+j-1].first].push_back(m_nodGrad[i-1].first);
                }
            }
            else
            {
                out<<"-1";
                return;
            }
            sort(m_nodGrad.begin()+i, m_nodGrad.end(),cmp);

        }
        int ok = 1;
        for(int i=0;i<m_nrNoduri;i++)
        {
            if(m_nodGrad[i].second != 0)
                ok = 0;
        }
        if(ok==1)
        {
            for(int i = 1; i <= m_nrNoduri; i++)
            {
                out<<i<<": ";
                for(int j = 0; j < m_list[i].size(); j++)
                {
                    out<<m_list[i][j]<<' ';
                }
                out<<'\n';
            }
        }
        else
        {
            out<<"-1";
            return;
        }

    }
    else
    {
        out<<"-1";
        return;
    }
}

void Graf::ctc_Kosoraju() //tare conexe
{

    in>>m_nrNoduri>>m_nrMuchii;
    for(int i=0;i<m_nrMuchii;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
        listAux[y].push_back(x);
    }
    for(int i=1;i<=m_nrNoduri;i++)
    {
        if(m_viz[i]==0)
        {
            r_dfs(i);
        }

    }
    for(int i=1;i<=m_nrNoduri;i++)
    {
        m_list[i].clear();
        for(int j=0;j<listAux[i].size();j++)
        {
            m_list[i].push_back(listAux[i][j]);
        }
    }

    for(int i=0; i<=m_nrNoduri;i++)
        m_viz[i]=0;
    for(int i=m_stiva.size()-1;i>=0;i--)
    {
        if(m_viz[m_stiva[i]]==0)
        {
            nrTC++;
            rr_dfs(m_stiva[i]);
        }


    }
    out<<nrTC<<'\n';
    for(int i = 1; i <= nrTC; i++)
    {
        for(int j = 0; j < tareConexe[i].size();j++)
            out<<tareConexe[i][j]<<' ';
        out<<'\n';
    }


}

void Graf::dijkstra()
{
    int contor = 0;
    in>>m_nrNoduri>>m_nrMuchii;
    for(int i=2;i<=m_nrNoduri;i++)
    {
        m_q[i]=1<<30;

    }
    m_q[1]=0;
    for(int i=1;i<=m_nrMuchii;i++)
    {
        int x,y,z;
        in>>x>>y>>z;
        v[x].push_back(y);
        d[x].push_back(z);
    }
    s.insert(make_pair(0,1));
    contor++;
    while(contor>0)
    {
        int w,q;
        w=s.begin()->first;
        q=s.begin()->second;
        if(m_viz[q]==1)
        {
            s.erase(s.begin());
            contor--;
        }
        else
        {
            m_viz[q]=1;
            int minim=1<<30;
            for(int i=0;i<v[q].size();i++)
            {
                if(m_q[v[q][i]]>m_q[q]+d[q][i])
                {

                    m_q[v[q][i]]=m_q[q]+d[q][i];
                    s.insert(make_pair(m_q[v[q][i]],v[q][i]));
                    contor++;

                }

            }
        }

    }
    for(int i=2;i<=m_nrNoduri;i++)
    {
        if(m_q[i]==1<<30)
            out<<"0 ";
        else
            out<<m_q[i]<<' ';
    }

}
void Graf::disjoint() {


    int n,m;
    in>>n>>m;
    for(int i=0; i<=n;++i) //parent 0 = 0 redundant(nu avem nod 0)
    {
        m_parent.push_back(i);
        m_rank.push_back(0);
    }

    for(int i=1;i<=m;++i)
    {
        int c,x,y; //cerinta,x,y
        in>>c>>x>>y;
        if(c==1)
        {
            this->union_(x, y);
        }
        if(c==2)
        {
            if(this->find(x) == this->find(y))
                out<<"DA\n";
            else
                out<<"NU\n";
        }


    }
}

int Graf::find(int x) {
    if(m_parent[x] != x)
        m_parent[x] = find(m_parent[x]);
    return m_parent[x];
}

void Graf::union_(int x, int y) {
    // gasesc reprezentantul multimii pt x si y
    int repx = find(x);
    int repy = find(y);
    if(repx == repy) return; //deja in aceeasi multime

    if(m_rank[repx] < m_rank[repy]) //leg multimea mai mica de multimea mai mare
        m_parent[repx] = repy;
    else if(m_rank[repy] < m_rank[repx])
        m_parent[repy] = repx;
    else                            //daca sunt egale leg y de x si rank x creste
    {
        m_parent[repy] = repx;
        m_rank[repx]++;
    }


}

void Graf::kruskal() {
    in>>m_nrNoduri>>m_nrMuchii;
    vector<edge> muchii,raspuns;
    int costTotal = 0;
    for(int i=0; i<=m_nrNoduri;++i) //parent 0 = 0 redundant(nu avem nod 0)
    {
        m_parent.push_back(i);
        m_rank.push_back(0);
    }

    for(int i=0;i<m_nrMuchii;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        edge aux;
        aux.x = x;
        aux.y = y;
        aux.cost = c;
        muchii.push_back(aux);
    }
    sort(muchii.begin(),muchii.end(),cmp_edge);
    for(int i=0;i<m_nrMuchii;++i)
    {
        if(this->find(muchii[i].x) != this->find(muchii[i].y))
        {
            raspuns.push_back(muchii[i]);
            costTotal += muchii[i].cost;
            union_(muchii[i].x, muchii[i].y);
        }

    }
    out<<costTotal<<'\n'<<raspuns.size()<<'\n';
    for (int i = 0; i < raspuns.size(); ++i) {
        out<<raspuns[i].x<<' '<<raspuns[i].y<<'\n';
    }
}

void Graf::bellmanFord() {
    vector<edge> muchii;
    in>>m_nrNoduri>>m_nrMuchii;

    for(int i=0;i<m_nrMuchii;++i)
    {
        int x,y,c;
        in>>x>>y>>c;
        edge aux;
        aux.x = x;
        aux.y = y;
        aux.cost = c;
        muchii.push_back(aux);
    }
    for(int i = 0; i <= m_nrNoduri; ++i)
    {
        m_parent.push_back(-1);
        m_distance.push_back(INT_MAX);
    }
    m_distance[1] = 0; //1 e nodul de plecare

    for(int i=0; i < m_nrNoduri-1; ++i)
    {
        for(int j=0; j<m_nrMuchii; ++j) //actualizam distantele in O(n*m)
        {
            if(m_distance[muchii[j].x] + muchii[j].cost < m_distance[muchii[j].y])
            {
                m_distance[muchii[j].y] = m_distance[muchii[j].x] + muchii[j].cost;
                m_parent[muchii[j].y] = muchii[j].x;
            }
        }
    }
    for(int j=0; j<m_nrMuchii; ++j) //actualizam distantele in O(n*m)
    {
        if(m_distance[muchii[j].x] + muchii[j].cost < m_distance[muchii[j].y])
        {
            out<<"Ciclu negativ!\n";
            return;
        }
    }
    for(int i=1;i<m_nrNoduri;i++)
    {
        out<<m_distance[i+1]<<' ';
    }
    out<<'\n';



}