#include<fstream>
#define Nmax 5001
#define infinit 20000

using namespace std;

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

int n,viz[Nmax],pre[Nmax];
int dist[Nmax];
short int c[Nmax][Nmax];

void citire()
{int i,j,x,y,m;
int cost;
fin>>n>>m;
for(i=1;i<=n;i++)
  for(j=i;j<=n;j++)
    {c[i][j]=infinit;
     c[j][i]=infinit;
    }
for(i=1;i<=n;i++)
   {dist[i]=infinit;
    c[i][i]=0;
   }
for(i=1;i<=m;i++)
 {fin>>x>>y>>cost;
  c[x][y]=cost;
 }
}

void dijkstra()
{int i,j,v;
int min;
dist[1]=0;
pre[1]=0;
for(i=1;i<n;i++)
  {min=infinit;
     for(j=1;j<=n;j++)
       if(!viz[j] && dist[j]<min)
         {v=j;
          min=dist[j];
         }
  viz[v]=1;
  for(j=1;j<=n;j++)
    if(dist[j]>dist[v]+c[v][j])
      {dist[j]=dist[v]+c[v][j];
       pre[j]=v;
      }
  }
}

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