#include<cstdio>
#include<vector>
#include<utility>
#include<queue>
#define oo 500000000
using namespace std;
vector <pair<int,int> > v[50010];
int n,m,viz[50010],cost[50010],trec_prin_nod[50010];
void citire()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            v[a].push_back(make_pair(b,c));
        }
}
void initializare()
{
    for(int i=1;i<=n;i++)
        cost[i]=oo;
}
void bellman_ford(int x0)
{
    queue<int> Q;
    int k;
    Q.push(x0);
    viz[x0]=1;
    cost[x0]=0;
    while(!Q.empty())
    {
        k=Q.front();
        Q.pop();
        viz[k]=0;
        for(vector <pair<int, int> >::iterator it=v[k].begin();it!=v[k].end();++it)
            if(cost[(*it).first]>cost[k]+(*it).second)
                {
                    cost[(*it).first]=cost[k]+(*it).second;
                    if(viz[(*it).first]==0)
                        {
                            Q.push((*it).first);
                            viz[(*it).first]=1;
                            trec_prin_nod[(*it).first]++;
                            if(trec_prin_nod[(*it).first]>n)
                            {
                                printf("Ciclu negativ!\n");
                                return;
                            }
                        }
                }
    }
}
void afisare()
{
    for(int i=2;i<=n;i++)
        if(cost[i]!=oo) printf("%d ",cost[i]);
        else printf("0 ");
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    initializare();
    bellman_ford(1);
    afisare();
    return 0;
}