#include <fstream>
#include <vector>
#define INF 999999
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int a[5000][5000];
int n,m;

void citire()
{
    fin>>n>>m;
    for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=n ; j++)
        a[i][j] = INF;
    while(m)
    {   int x,y,z;
        fin>>x>>y>>z;
        a[x][y] = z;
        m--;
    }
}
int d[50000];

void dijkstra()
{
    int t[50000],p[50000];///lista de tati, de distante, pus/ nepus;
    d[1]=0;
    p[1] = 1;
    for(int i=2 ; i<=n ; i++)
        {d[i]=a[1][i];
            if(d[i]!=0)t[i] = 1;
        }
    for(int k=1 ; k<=n-1 ; k++)
    {

        int minn = 9999,L;
        for(int i=2 ; i<=n ; i++)
            if(p[i]!=1)
            if(d[i] <  minn )minn=d[i],L=i;

        {
            for(int j=2 ; j<=n ; j++)
            if(p[j]!=1)
                if(a[L][j] + d[L] < d[j] )
                    d[j]=a[L][j]+d[L],t[j]=L;


            p[L]=1;
        }

    }
    for(int i=2; i<=n ; i++)
        fout<<d[i]<<" ";

}

int main()
{
    citire();
    dijkstra();

    return 0;
}