#include <fstream>
#include <vector>

#define NMAX 50010
#define INF 999999


using namespace std;

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

int n, m, t, x, a, b, c, i, j, minu, poz;
int dist_1[NMAX], dist_2[NMAX], tata[NMAX];
vector<int> M[NMAX], C[NMAX];
bool v[NMAX], okay;

void dijkstra(int x);

int main()
{
    //fin >> t;
    //for(i = 1; i <= t; ++i)
    {

        fin >> n >> m;
        //fin >> x;
        for(j = 1; j <= n; ++j)
            {
                //fin >> dist_1[j];
                tata[j] = x;
                dist_2[j] = INF;
                v[j] = false;
            }
        for(j = 1; j <= m; ++j)
        {
            fin >> a >> b >> c;
            M[a].push_back(b);
            //M[b].push_back(a);

            C[a].push_back(c);
            //C[b].push_back(c);
        }
        dijkstra(1);
        for(j = 2; j <= n; ++j)
            fout << dist_2[j] << ' ';
        /*okay = false;
        for(j = 1; j <= n; ++j)
            if(dist_1[j] != dist_2[j])
            {
                okay = true;
                break;
            }
        if(okay == true)
            fout << "NU\n";
        else
            fout << "DA\n";
            */
    }

    return 0;
}

void dijkstra(int x)
{
    int i, j;
    for(i = 0; i < M[x].size(); ++i)
        dist_2[M[x][i]] = C[x][i];
    dist_2[x] = 0;
    tata[x] = 0;
    v[x] = true;
    okay = true;
    while(okay)
    {
        minu = INF;
        for(j = 1; j <= n; ++j)
            if(v[j] == false && minu > dist_2[j])
        {
            minu = dist_2[j];
            poz = j;
        }
        if(minu != INF)
        {
            v[poz] = true;
            for(j = 0; j < M[poz].size(); ++j)
                if(v[M[poz][j]] == false && dist_2[M[poz][j]] > dist_2[poz] + C[poz][j])
                {
                    dist_2[M[poz][j]] = dist_2[poz] + C[poz][j];
                    //v[M[poz][j]] = true;
                }
        }
        else
            okay = false;
    }
}