#include <cstdio>
#include <vector>
#include <queue>
#define INF 2000000000
using namespace std;

struct Nod{int x,cost;};
vector <Nod> L[50005];
queue <int> Q;
int n, m, d[50005], ord[50005];
void Read()
{
    Nod aux;
    int i,k;
    freopen("bellmanford.in","r",stdin);
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d", &k, &aux.x, &aux.cost);
        L[k].push_back(aux);
    }
}
void Initializare(int nodSursa)
{
    for(int i=1; i<=n; i++)
        d[i] = INF;
    d[nodSursa] = 0;
}
bool Bellmanford(int nodSursa)
{
    Initializare(nodSursa);
    Nod aux;
    int k;
    vector<Nod>::iterator it;
    Q.push(nodSursa);
    while(!Q.empty())
    {
        k = Q.front();
        Q.pop();
        for(it = L[k].begin();it!= L[k].end(); it++)
        {
            aux = *it;
            if(d[aux.x] > d[k] + aux.cost)
            {
                d[aux.x] = d[k] + aux.cost;
                Q.push(aux.x);
                if(d[aux.x] > d[k] + aux.cost)
                    return false;
            }
        }
    }
    return true;
}
int main()
{
    Read();
    bool ans = Bellmanford(1);
    if(!ans)
    {
        freopen("bellmanford.out","w",stdout);
        printf("Ciclu negativ!");
        return 0;
    }
    freopen("bellmanford.out","w",stdout);
    for(int i=2; i<=n; i++)
        if(d[i] != INF)
            printf("%d ", d[i]);
    printf("\n");
    return 0;
}