#include <bits/stdc++.h>

using namespace std;

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

int n,m;
vector <pair <int,int>> adiacenta[50010];
int fr[50000],d[5000];
vector<bool>vizitat;
queue <int>q;

void BF(int i)
{
    d[i] = 0;
    vizitat[i] = true;
    q.push(i);

    while(!q.empty())
    {
       int vf = q.front();
       q.pop();
       vizitat[vf] = true;
       fr[vf]++;
       if(fr[vf] > n)
       {
           out<<"Ciclu negativ!\n";

       }
       else
        {
            for (auto vecin:adiacenta[vf])
            {

                if(d[vecin.first] > vecin.second + d[vf])
                {
                    d[vecin.first] = vecin.second + d[vf];
                    if(!vizitat[vecin.first])
                    {
                        q.push(vecin.first);
                    }

                }
            }

       }
    }


}

int main()
{

    int x,y,c;
    in>>n>>m;

    for(int i = 1; i <= n; i++)
        d[i] = 2e9;

    for(int i = 1; i <= m; i++)
    {

        in>>x>>y>>c;
        adiacenta[x].push_back(make_pair(y,c));//graf orientat
    }

    vizitat.assign(n+1,false);
    BF(1);

    for(int i = 2; i<= n; i++)
    {
        out<<d[i]<<" ";
    }
    out<<"\n";

    return 0;
}