#include <fstream>
#include <cstring>
#include<vector>
#include <climits>

#define MAXN 50002

using namespace std;

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

int x, y, z, n, m;
int cost[MAXN], viz[MAXN];

struct punct{
    int c, graf;
};

vector <punct> G[MAXN];

inline void Read()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;

        G[x].push_back({z, y});
    }

   for (int i = 1; i <= n; i++)
    cost[i] = INT_MAX;
}

inline void Solve()
{
    int minim, poz;
    cost[1] = 0;

    for (int i = 1; i <= n; i++)
    {
        minim = INT_MAX;

        for (int j = 1; j <= n; j++)
        {
            if (cost[j] < minim && viz[j] == 0)
            {
                minim = cost[j];
                poz = j;
            }
        }
        //int l = G[poz].size();

        for (vector <punct> :: iterator j = G[poz].begin(); j != G[poz].end(); j++)
        {
            if (viz[(*j).graf] == 0)
            {
                if (cost[poz] + (*j).c < cost[(*j).graf])
                {
                    cost[(*j).graf] = cost[poz] + (*j).c;
                }
            }
        }

        viz[poz] = 1;
    }
}

inline void Afisare()
{
    for (int i = 2; i <= n; i++)
    {
        fout << cost[i] << " ";
    }
}

int main ()
{
    Read();
    Solve();
    Afisare();

    fin.close(); fout.close(); return 0;
}