#include<fstream>
#define infinit 4000000

using namespace std;

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

unsigned int  a[5000][5000],n,m,viz[5000],dist[5000],coada[5000],p,u;

void citire()
{unsigned int x,y,cost,i;
fin>>n>>m;
for(i=1;i<=m;i++)
  {fin>>x>>y>>cost;
   a[x][y]=cost;
  }
}

void determinare() //dijkstra
{unsigned int j,i,aux;
//initializare
p=1,u=1;
coada[p]=1;
for(i=2;i<=n;i++)
 dist[i]=infinit;
while(p<=u)
   {p++;aux=coada[p-1];
   if(viz[aux]==0)
    {viz[aux]=1;
     for(j=1;j<=n;j++)
      if(a[aux][j]!=0)
        if(dist[j]>dist[aux]+a[aux][j])
          {dist[j]=dist[aux]+a[aux][j];
           u++;
           coada[u]=j;
          }
    }
   }
for(i=2;i<=n;i++)
  if(dist[i]!=infinit)
     fout<<dist[i]<<" ";
    else fout<<"0 ";
}


int main()
{citire();
determinare();
fin.close();
fout.close();
return 0;
}