#include <fstream>
#include <iostream>
#include <math.h>
using namespace std;
fstream g("dijkstra.out",ios::out);
const float Pinfinit=1.e20;
float A[50][50],D[50],min;
int S[50],T[50],n,I,j,r,poz;
void Citire_cost (char Nume_fis[20],float A[50][50],int& n)
{
int I,j,m;
float c;
fstream f("dijkstra.in",ios::in);
f>>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]=Pinfinit;
while (f>>I>>j>>c) A[I][j]=c;
f.close();
}
void drum(int I)
{
if (T[I]) drum(T[I]);
g<<I<<" ";
}
main()
{ float min;
Citire_cost("dijkstra.in",A,n);
r=1;S[r]=1;
for (I=1;I<=n;I++)
{
D[I]=A[r][I];
if (I!=r)
if (D[I]<Pinfinit) T[I]=r;}
for (I=1;I<=n;I++)
{
min=Pinfinit;
for(j=1;j<=n;j++)
if (S[j]==0)
if (D[j]<min)
{
min=D[j];
poz=j;
}
S[poz]=1;
for (j=1;j<=n;j++)
if (S[j]==0)
if (D[j]>D[poz]+A[poz][j])
{
D[j]=D[poz]+A[poz][j];
T[j]=poz;
}
}
for (I=1;I<=n;I++)
if (I!=r)
if(T[I])
{
g<<D[I]<<" ";
}
}