#include <iostream>
#include <fstream>

using namespace std;

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

int n,i,k,j,a[50000][50000];
struct st{
       int d,r,s;
       };
       st b[50000];
       
void dj(){
     int p=1;
     int minn,im;
     while(p!=n){
           for(i=1;i<=n;i++){
                             minn=99999;
           if(p!=i && a[p][i]!=0){ 
                   b[i].d= min(b[i].d,b[p].d+a[p][i]);      
                   if (b[i].d<minn && b[i].s==0) { minn=b[i].d;  } 
                   }
                 }
                 minn=9999;
                 for(i=2;i<=n;i++) if(b[i].d<minn && b[i].s==0) {minn=b[i].d; im=i;}
                 b[im].s=1;
                 b[p].r=im;       
                 p=im;
                 }
     }

          
          
int main(){
    int a1,b1,c,m;
    fin>>n>>m;
    for (i=2;i<=n;i++) b[i].d=99999;
    b[i].s=1;
    for(i=1;i<=m;i++) { fin>>a1>>b1>>c; a[a1][b1]=c; } 
//cout<<n;
dj();
for (i=1;i<=n;i++)
fout<<b[i].d<<" ";

    
 //   system("pause");
 return 0;   
}