#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <process.h>
typedef struct nod{
    int i,c;
    struct nod *urm;}NOD;
#define MAX 999999
#define EEE 100
long d[EEE];
int s[EEE];
NOD *v[EEE];
long n,m;

void citire()
{
    int i,x,y,c;
    NOD *p;
    FILE *f;
    f=fopen("c:\\dijkstra.in","r");
    if (f==0) printf("fsdfsd");
    fscanf(f,"%ld %ld",&n,&m);
    for(i=0;i<=n;i++) d[i]=MAX;
    for(i=0;i<m;i++)
     {
         p=(NOD*)malloc(sizeof(NOD));
         fscanf(f,"%d %d %d",&x,&y,&c);
         p->i=y; p->c=c;
         p->urm=v[x];v[x]=p;
     }
     fclose(f);
}
void dijkstra()
{
    NOD *p;
    long min,cmin,i,j;
 p=v[1];
 while (p)
       {
           d[p->i]=p->c;
           p=p->urm;
       }
s[1]=1;
for(i=1;i<n;i++)
 {
     cmin=MAX;
     for(j=2;j<=n;j++)
        {

        if ((s[j]==0)&&(d[j]<cmin))
                 {
                     min=j; cmin=d[j];
                 }
        }
    if(cmin==MAX)
    {   printf("nu-i bine ");
        break;
        }
    p=v[min];
    s[min]=1;
       while(p)
       {
        if (d[p->i]>d[min]+p->c)
                   d[p->i]=d[min]+p->c;
          p=p->urm;
       }
 }
}
 void afis()
 {
     long i;
     FILE *f;
 f=fopen("dijkstra.out","w");
     for(i=2;i<=n;i++)
      if (d[i]==MAX) fprintf(f,"0 ");
         else fprintf(f," %ld ",d[i]);
 fclose(f);
 }
 int main()
{
    citire();
    dijkstra();
    afis();
    return 0;
}