#include <fstream>
#define inf 10000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int a[10001][10001],dmin[10001],viz[10001];
int n,m;
void citire(){
f>>n>>m;
int x,y;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
    a[i][j]=inf;
for(int i=1;i<=n;i++)
    dmin[i]=inf;
while(f>>x>>y) f>>a[x][y];
}
void dijkstra(int nod){
dmin[nod]=0;
for(int i=1;i<=n;i++){
int dist=inf;
int nodc;
for(int i=1;i<=n;i++)
    if(dmin[i]<dist && !viz[i]) {dist=dmin[i]; nodc=i;}
viz[nodc]=1;
for(int i=1;i<=n;i++){
    if(a[nodc][i] && dmin[i]>dist+a[nodc][i]) dmin[i]=dist+a[nodc][i];
}
}
for(int i=2;i<=n;i++)
    if(dmin[i]==inf) g<<"0 ";
    else
    g<<dmin[i]<<" ";
}
int main()
{
    citire();
    dijkstra(1);
    return 0;
}