#include <fstream>
#include <climits>
#include <vector>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define maxvalue 50005

int viz[maxvalue], cost[maxvalue], index, cost_min, node, first, second, n, m;
vector<pair<int, int>> graf[maxvalue];
pair<int, int> mypair;

void Dijkstra(int node)
{
    for (int i = 0; i < graf[node].size(); i ++)
    {
        mypair = graf[node][i];
        if ((cost[node] + mypair.second) < cost[mypair.first])
            cost[mypair.first] = cost[node] + mypair.second;
    }
}
int main()
{
    f >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        f >> node >> first >> second;
        mypair = make_pair(first, second);
        graf[node].push_back(mypair);
    }
    for (int i = 1; i <= n; i ++)
        cost[i] = INT_MAX;

    viz[1] = 1;
    cost[1] = 0;
    Dijkstra(1);

    while (cost_min != INT_MAX)
    {
        cost_min = INT_MAX;
        for (int i = 1; i <= n; i ++)
            if (cost[i] < cost_min && !viz[i])
            {
                cost_min = cost[i];
                index = i;
            }
        if (cost_min != INT_MAX)
        {
            Dijkstra(index);
            viz[index] = 1;
        }
    }

    for (int i = 2; i <= n; i ++)
        g << cost[i] << " ";

    f.close();
    g.close();
    return 0;
}