#include <iostream>
#include <fstream>
#include <climits> // ca sa folosesti INT_MAX

using namespace std;
int n,m,x,viz[100], s[100], p[100],y,mini,a[100][100];// viz -> pentru vizitare; s->costul drumului
                                            // p-> pozitia anterioara nodului
void citire()
{
    ifstream f("dijkstra.in");
    int x,y,c;
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i!=j && a[i][j]==0)
                a[i][j]=INT_MAX/2; // aici pui infinit in matrice unde nu ai legaturi
}
void dir()
{
    viz[x]=1; // ai vizitat nodul sursa. duuuh
    for(int i=1; i<=n; i++)
    {
        s[i]=a[x][i]; // populezi vectorul suma
        if(i!=x && s[i]<INT_MAX/2)p[i]=x; // daca ai legaturi, atunci poti sa mergi acolo, din x
    }
    for(int i=1; i<n; i++)
    {
        mini=INT_MAX;
        for(int j=1; j<=n; j++)
            if(viz[j]==0 && s[j]<mini)// daca nu am trecut pe acolo si am legatura
            {
                mini=s[j];//iau suma minima
                y=j;//retin pozitia unde este drumul cu cel mai mic cost
            }
        viz[y]=1;// ma duc in nodul respectiv
        for(int i=1; i<=n; i++)
            if(viz[i]==0 && s[i]>s[y]+a[y][i])//recalculez drumul mini in toate punctele trecand prin punctul y
            {
                s[i]=s[y]+a[y][i];
                p[i]=y;
            }
    }
}
int main()
{
    citire();
    x=1;
    dir();
    ofstream g("dijkstra.out")
    for(int i=2; i<=n; i++)
        g<<s[i]<<' ';
    return 0;
}