#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
#define NMAX 50005
#define INF 1000000000

using namespace std;

FILE * fin = freopen("bellmanford.in", "r", stdin);
FILE * fout = freopen("bellmanford.out", "w", stdout);

vector<pair<int, int> > graf[NMAX];
queue<int> C;
int dmin[NMAX], nr[NMAX], pred[NMAX], n, m;

void citire()
{
    int i, x, y, cost;
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d", &x, &y, &cost);
        graf[x].push_back(make_pair(y, cost));
    }
}
bool bellmanford();
void afisare()
{
    int i;
    printf("%d", dmin[2]);
    for(i=3;i<=n;++i)
        printf(" %d", dmin[i]);
    printf("\n");
}

int main()
{
    citire();
    if(bellmanford()==false)
        printf("Ciclu negativ!\n");
    else
        afisare();
    return 0;
}

bool bellmanford()
{
    int i, x, y, cost;
    for(i=2;i<=n;++i)
    {
        dmin[i]=INF;
        pred[i]=1;
    }
    C.push(1);
    nr[1]++;
    while(!C.empty())
    {
        x=C.front();
        C.pop();
        for(i=0;i<graf[x].size();++i)
        {
            y=graf[x][i].first;
            cost=graf[x][i].second;
            if(dmin[y]>dmin[x]+cost)
            {
                dmin[y]=dmin[x]+cost;
                pred[y]=x;
                C.push(y);
                nr[y]++;
                if(nr[y]==n)
                    return false;
            }
        }
    }
    return true;
}