#include <stdio.h>
#include <vector>
#include <bitset>
#include <string.h>
const long inf=1<<30;
using namespace std;
struct graf{long gf; long val; } aux;
vector <graf> v[50000];
bitset <50000> bif;
vector <int> t;
long s[50000];
int main() {
FILE *f,*g;
int n,m,i,j,x,y,z;
int min,minp;
f=fopen("dijkstra.in","r");
g=fopen("dijkstra.out","w");
fscanf(f,"%d%d",&n,&m);
//memset(s,inf,sizeof(s) );
for (i=1;i<=n;i++) s[i]=inf;
s[1]=0;
for (i=1;i<=m;i++) {
                fscanf(f,"%d%d%d",&x,&y,&z);
                if (x==1) s[y]=z;
                aux.gf=y;
                aux.val=z;
                v[x].push_back(aux);
                    }

bif[1]=1;
for (i=2;i<=n;i++)  {
min=inf;
minp=0;
for (j=1;j<=n;j++)
if (s[j]<min && bif[j]==0) {
                            minp=j;
                            min=s[j];
                            }
bif[minp].flip();
for (j=0;j<v[minp].size();j++)
        if (s[v[minp][j].gf]>s[minp]+v[minp][j].val) {s[v[minp][j].gf]=s[minp]+v[minp][j].val; }

}
for (i=2;i<=n;i++)
 if (s[i]==inf) fprintf(g,"0 ");
 else
 fprintf(g,"%ld ",s[i]);
fclose(g);
return 0;
}