#include<iostream>
#include<fstream>
#include<limits>
using namespace std;

typedef struct matrice
{
	int **mat,m,n;
	matrice()
	{
			m=0;n=0;mat=NULL;
	}
	matrice(int a,int b)
	{
		mat=new int*[a];
		for(int i=0;i<a;i++)mat[i]=new int[b];
		m=a;
		n=b;
	}
} matrice;

matrice* citeste_graf(const char* filename, int &n)
{
    ifstream in(filename);
    in>>n;
    matrice *matr=new matrice(n, n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            matr->mat[i][j]=0;
    int a, b, cost;
    int i;
    in>>i;
    for(int j=0; j<i; j++)
    {
        in>>a>>b>>cost;
        a--; b--;
        matr->mat[a][b]=matr->mat[b][a]=cost;
    }
    return matr;
}

void dijkstra(matrice* mat, int sursa, int*dist, int*tata)
{
    const  int INF=numeric_limits<int>::max();
    int n=mat->n;
    for(int i=0; i<n; i++)
    {
        dist[i]=INF;
        tata[i]=-1;
    }
    dist[sursa]=0;
    bool* viz=new bool[n];
    for(int i=0; i<n; i++) viz[i]=false;
    bool gata=false;
    while(!gata)
    {
        int min=INF, i_min=0;
        for(int i=0; i<n; i++) 
            if(!viz[i]&&dist[i]<min)
            {
                min=dist[i];
                i_min=i;
            }
        viz[i_min]=true;
        
        for(int j=0; j<n; j++)
            if(mat->mat[i_min][j]&&!viz[j])
            {
                if(dist[i_min]==INF)
                {
                    dist[i_min]=mat->mat[i_min][j];
                    tata[j]=i_min;
                }
                else
                {
                    int alt=dist[i_min]+mat->mat[i_min][j];
                    if(alt<dist[j])
                    {
                        dist[j]=alt;
                        tata[j]=i_min;
                    }
                }
            }
        
        gata=true;
        for(int i=0; i<n; i++)
            if(!viz[i])
            {
                gata=false;
                break;
            }
    }
}
        
int main()
{
    int n;
    matrice* m=citeste_graf("dijkstra.in", n);
    int* dist=NULL, *tata=NULL;
    dist=new int[n], tata=new int[n];
    dijkstra(m, 0, dist, tata);
    ofstream out("dijkstra.out");
    for(int i=0; i<n; i++)
        out<<dist[i]<<' ';
    cout<<'\n';
}