#include <fstream>
#include <queue>
#define infinity 1000000000
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

long long a[10000][10000];
int n,m,x,y,c,nd[50001];
bool e_in_q[10000];
int verif[10000];
queue<int> q;
bool ok=1;
void Ford(int nod)
{
    q.push(1);
    for(int i=1;i<=n;i++)
    {
        if(a[1][i]!=0&&a[1][i]!=infinity)
        {
            q.push(i);
            nd[i]=a[1][i];
        }
    }
    q.pop();
    while(!q.empty())
    {

        int nod_curent=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(a[nod_curent][i]!=0&&a[nod_curent][i]!=infinity)
            {
                if(a[nod_curent][i]+nd[nod_curent]<nd[i]&&e_in_q[nod_curent]==0)
                {

                    q.push(i);
                    verif[i]++;
                    e_in_q[i]=1;
                    nd[i]=a[nod_curent][i]+nd[nod_curent];
                    if(verif[i]>n)
                    {
                        cout<<"Ciclu negativ!";
                        ok=0;
                        return;
                    }
                }
            }
        }
        e_in_q[nod_curent]=0;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            a[i][j]=infinity;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        a[x][y]=c;
    }
    for(int i=2;i<=n;i++)
        nd[i]=infinity;
    Ford(1);
    if(ok==0) return 0;
    for(int i=2;i<=n;i++)
        cout<<nd[i]<<" ";
}