#include<iostream>
#include<fstream>
#define INF 0x3f3f3f3f

using namespace std;

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

struct nod {
        int info,cost;
        nod *urm;
        };
nod *prim[50010], *a;

int n,m,d[50010],x,y,c[50010],u,p,ct,viz[50010];

void insert(int x, int y, int c)
{       a=new nod;
        a->info=y;
        a->cost=c;
        a->urm=prim[x];
        prim[x]=a;
}

void bellmanFord()
{       nod *q;
        int i,X;
        for(i=1;i<=n;i++) d[i]=INF;
        d[1]=0;
        p=u=1;
        c[p]=1;
        int m=1;
        while(p<=u)
        {       X=c[p++];viz[X]=0;
                for(q=prim[X];q;q=q->urm)
                        if(d[X]+q->cost<d[q->info])
                        {
                            d[q->info]=d[X]+q->cost; cout<<"Pasul "<<m<<endl; for(int j=1;j<=n;j++)  cout<<"d["<<j<<"]="<<d[j]<<" ";
                                                                                             cout<<endl;
                                                                                             m++;
                                if(!viz[q->info])
                                {       u++;
                                        c[u]=q->info;
                                        for(int j=1;j<=n;j++)  cout<<"c["<<j<<"]="<<c[j]<<" ";
                                                                                             cout<<endl;
                                        viz[q->info]=1;
                                        for(int j=1;j<=n;j++)  cout<<"viz["<<j<<"]="<<viz[j]<<" ";
                                                                                             cout<<endl;
                                }
                        }
        }
}

void write()
{       int i;
        for(i=2;i<=n;i++)
        {       if(d[i]!=INF)
                        fout<<d[i]<<' ';
                else    fout<<"0 ";
        }
}

int main()
{       int i;
        fin>>n>>m;
        for(i=1;i<=m;i++)
        {       fin>>x>>y>>ct;
                insert(x,y,ct);
        }
        bellmanFord();
        write();
        return 0;
}