#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 1000000007

using namespace std;

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

struct varf{int x, c;};

int n,m;
int cmin[NMAX],nr[NMAX];
bool ciclu_negativ=0;
vector<varf> G[NMAX];

queue<int> C;

void Bellman_Ford(int start);

int main()
{
    int i,x,y,c;
    varf vf;

    fin>>n>>m;

    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        vf.x=y; vf.c=c;
        G[x].push_back(vf);
    }

    Bellman_Ford(1);

    if(ciclu_negativ)
    {
        fout<<"Ciclu negativ!";
        return 0;
    }

    for(i=2; i<=n; i++)
        fout<<cmin[i]<<' ';

    return 0;
}

void Bellman_Ford(int start)
{
    int i,x;

    for(i=1; i<=n; i++)
        cmin[i]=INF;
    cmin[start]=0;
    C.push(start);

    while(!C.empty() && !ciclu_negativ)
    {
        x=C.front(); C.pop();
        for(i=0; i<G[x].size(); i++)
            if(cmin[x]+G[x][i].c<cmin[G[x][i].x])
            {
                cmin[G[x][i].x]=cmin[x]+G[x][i].c;
                nr[G[x][i].x]++;
                if(nr[G[x][i].x]==n)
                    break;
                C.push(G[x][i].x);
            }
    }
}