#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];

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 i,j;
//initializare
for(i=2;i<=n;i++)
 dist[i]=infinit;
for(i=1;i<=n;i++)
  if(viz[i]==0)
    {viz[i]=1;
     for(j=1;j<=n;j++)
      if(a[i][j]!=0)
        if(dist[j]>dist[i]+a[i][j])
          dist[j]=dist[i]+a[i][j];
    }
for(i=2;i<=n;i++)
  fout<<dist[i]<<" ";
}


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