#include <fstream>
#include <cstring>
#define MAX_N 50001
#define MAX_M 250001
#define INF 0x3f3f3f3f
using namespace std;
int m,n,s,e[MAX_M][3],d[MAX_N],ciclu;
ofstream g("bellmanford.out");
void rez(int s)
{
    int ok,nr,i,j,c,k;
    memset(d,INF,sizeof(d));
    d[s]=0;
    for(ok=nr=1;ok&&nr<n;nr++)
        for(ok=k=0;k<m;k++)
        {
            i=e[k][0];
            j=e[k][1];
            c=e[k][2];
            if(d[j]>d[i]+c)
            {
                d[j]=d[i]+c;
                ok=1;
            }
        }
    for(k=0;k<m;k++)
    {
        i=e[k][0];
        j=e[k][1];
        c=e[k][2];
        if(d[j]>d[i]+c)
        {
            g<<"Ciclu negativ!";
            ciclu=true;
            break;
        }
    }

}
int main()
{
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(int i=0;i<m;i++)
        f>>e[i][0]>>e[i][1]>>e[i][2];
    f.close();
    rez(1);
    if(ciclu) return 0;
    for(int i=2;i<=n;i++)
        if(d[i]!=INF)g<<d[i]<<" ";
        else g<<"0 ";
    g.close();
    return 0;
}