#include<fstream>
#define nmax 50001
#define infinit 200000

using namespace std;

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

int n;

struct nod
  {int info,cost;
  nod *urm;
  };
nod *l[nmax];

int dist[nmax],viz[nmax];

void citire()
{int x,y,cost,m,i;
fin>>n>>m;
for(i=1;i<=m;i++)
  {fin>>x>>y>>cost;
   nod *c;
   c=new nod;
   c->info=y;
   c->cost=cost;
   c->urm=l[x];
   l[x]=c;
  }
}

void initializare()
{int i;
for(i=1;i<=n;i++)
  dist[i]=infinit;
dist[1]=0;

}

void dijkstra()
{int i,min,v,j;
for(i=1;i<n;i++)
  {min=infinit;
  for(j=1;j<=n;j++)
     if(viz[j]==0 && dist[j]<min)
       {min=dist[j];
        v=j;
       }
  viz[v]=1;
  for(nod *c=l[v];c!=NULL;c=c->urm)
    if(c->cost+dist[v]<dist[c->info])
      dist[c->info]=dist[v]+c->cost;
  }
}

int main()
{citire();
initializare();
dijkstra();
for(int i=2;i<=n;i++)
  if(dist[i]!=infinit) fout<<dist[i]<<" ";
    else fout<<"0 ";
fin.close();
fout.close();
return 0;
}