#include <fstream>
#include <climits>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
struct per
{
    int nr=0;
   vector <int > des,c;
}v[50005];

int n,m;
int viz[50005];
bool rec[50005];
bool f=0;
int cost[50005];

int bellman()
{
    queue <int> q;
    q.push(1);
    cost[1]=0;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        viz[t]++;
        if(viz[t]>n)
        {
            f=1;
            cout<<"Ciclu negativ!";
            return 0;
        }
        rec[t]=0;

        int cnt=0;
        for(auto it:v[t].des)
        {
            if(cost[it]>v[t].c[cnt]+cost[t])
            {
                cost[it]=v[t].c[cnt]+cost[t];

                if(rec[it]==0)
                {
                    rec[it]=1;
                     q.push(it);
                }


            }
            cnt++;



        }





    }




return 0;
}




int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cost[i]=(1<<30);
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,co;
        cin>>a>>b>>co;
        v[a].des.push_back(b);
        v[a].c.push_back(co);
        v[a].nr++;
    }
    bellman();
    if(f==0)
    for(int i=2;i<=n;i++)
    {
        cout<<cost[i]<<" ";
    }




    return 0;
}