#include <stdio.h>
#include <malloc.h>

#define NEDGES 250000
#define NPOINTS 50000
#define INFI 999999

//using namespace std;

struct muchie
{
int fin,dst;
};

int n,m;

muchie *x[NPOINTS+1];
int l[NPOINTS+1];

void cit()
{
int i;
int a,b,c,d;
FILE *f=fopen("dijkstra.in","r");
fscanf(f,"%d %d",&n,&m);

for(i=0;i<m/4;i++)
        {
        fscanf(f,"%d %*d %*d\n%d %*d %*d\n%d %*d %*d\n%d %*d %*d\n",&a,&b,&c,&d);
        ++l[a];++l[b];++l[c];++l[d];
        }

for(i=0;i<m%4;i++)
        {
        fscanf(f,"%d %*d %*d\n",&a);
        ++l[a];
        }
for(i=1;i<=n;i++)
{
x[i]=(muchie*)malloc(sizeof(muchie)*(l[i]+1));
l[i]=0;
}

fclose(f);
f=fopen("dijkstra.in","r");
fscanf(f,"%*d %*d\n");
for(i=0;i<m;i++)
        {
        fscanf(f,"%d %d %d\n",&a,&b,&c);
        x[a][l[a]].fin=b;
        x[a][l[a]].dst=c;
        l[a]++;
        }
fclose(f);
}

void tip(int a)
{
int i;
for(i=0;i<l[a];i++)
{
printf("%d %d %d\n",a,x[a][i].fin,x[a][i].dst);
}
}

int dist[NPOINTS];

void distmin(int sursa)
{
int i,j,k;
int t;
for(i=0;i<=n;i++)dist[i]=INFI;
dist[sursa]=0;
for(k=0;k<n;k++)
for(i=1;i<=n;i++)
for(j=0;j<l[i];j++)
        {
        t=dist[i]+x[i][j].dst;
        if(dist[x[i][j].fin]>t)
        dist[x[i][j].fin]=t;
        }
}

void tip()
{
int  i;
FILE *f=fopen("dijkstra.out","w");
for(i=2;i<n;i++)
if(dist[i]!=INFI)
fprintf(f,"%d ",dist[i]);
else
fprintf(f,"0 ");
if(dist[n]==INFI)
fprintf(f,"0\n");
else
fprintf(f,"%d\n",dist[n]);
fclose(f);
}

int main()
{
cit();
distmin(1);
tip();
return 0;
}