#include <iostream>
#include <fstream>

using namespace std;

int v[5000][5000], s[25000], d[2500], t[25000];

void drum(int i)
{
    if(t[i]) drum(t[i]); cout<<i<<" ";
}
int main()
{
 int inf=3000, r=1, n, m, poz, min;

    ifstream f("alex.in");
    f>>n>>m;

    //for(int i=1;i<=n;i++)
      //  for(int j=1;j<=n;j++)
        //    v[i][j]=3500;

    for(int y=1;y<=m;y++)
    {int x, y, z;
        f>>x>>y>>z;
        v[x][y]=z;
    }

    s[r]=1;
    for(int i=1;i<=n;i++)
    {
        d[i]=v[r][i];
        if(i!=r && d[i]<inf)
            t[i]=r;
    }

    for(int i=1;i<=n-1;i++)
    {
        min=inf;
        for(int j=1;j<=n;j++)
            if(!s[j] && d[j]<min)
            {
                min=d[j];
                poz=j;
            }
        s[poz]=1;

        for(int j=1;j<=n;j++)
            if(!s[j] && d[j]>d[poz]+v[poz][j])
            {
                d[j]=d[poz]+v[poz][j];
                t[j]=poz;
            }
    }

    ofstream g("dijkstra.out");
    for(int i=2;i<=n;i++)
    g<<d[i]<<" ";

    return 0;

}