#include<bits/stdc++.h>
#define Inf 10000
using namespace std;
int n,circuit=0,viz[100]={0},a[20][20],a2[20][20];
void citire(int a[][100],int &n)
 {  int m,i,j;
     ifstream fin("dijkstra.in");
     fin>>n>>m;
     for( i=1;i<=n;i++)
        for( j=1;j<=n;j++)
        if(i==j) a[i][j]=0;
        else a[i][j]=Inf;

     for(i=1;i<=m;i++)
     {int x,y,z;
         fin>>x>>y>>z;
         a[x][y]=z;
     }

}
void afisare(int a[][100],int n)
{
    int i,j;
    for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
        cout<<a[i][j]<<" ";
        cout<<endl;
    }
}
void royfloyd(int a[][100],int n)
{
    int i,j,k;
    for(k=1;k<=n;k++)
        {for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
          if(a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j];
          //pred[k]=i,pred[j]=k;
         // afisare(a,n);
         // cout<<endl;
        }

}

void dijkstra(int a[][100],int n,int x,int pred[],int d[])
{
    int i,j,k,viz[100]={0},aa,y;
    for(i=1;i<=n;i++)
    {
        d[i]=a[x][i];
        pred[i]=x;
    }
    pred[x]=0;
    viz[x]=1;

    for(i=1;i<=n-1;i++)
    {
        aa=Inf;
        for(j=1;j<=n;j++) if(d[j]<aa && !viz[j])
        {
            aa=d[j];
            y=j;
        }
        if(aa!=Inf)
        {
            viz[y]=1;
        for(j=1;j<=n;j++)
            if(!viz[j] && d[j]>d[y]+a[y][j])
        {  d[j]=d[y]+a[y][j];
        pred[j]=y;

        }
        }

    }

}

void Afisare(int pred[100],int y)
{
    int i,j,k;
    while(y)
    {
        cout<<y;
        y=pred[y];
    }

}

void Afisare_r(int pred[],int y)
{
    if(y) {Afisare_r(pred,pred[y]);
    cout<<y;}
}

int main()
{   int a[100][100],i,j,n,pred[100],d[100],y;
    citire(a,n);
    //royfloyd(a,n);
   // afisare(a);
//cout<<sizeof(long long);
//t:sa se afiseze costul minim pentru drumul dintre 2 noduri x si y si drumul .
dijkstra(a,n,1,pred,d);
ofstream g("dijkstra.out");
for(i=2;i<=n;i++) g<<d[i]<<' ';

//for(i=1;i<=n;i++) cout<<d[i]<<" ";
//cin>>y;
//Afisare(pred,y);
//cin>>y;
//Afisare_r(pred,y);
//t:sa se afiseze drumul minim dintre nodul x si oricare alt nod din graf, folosind dijkstra
//t:bile si auto

}