#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX = 50000;

struct edge
{
    int dest, cost;
};

vector <edge> graph[NMAX + 5];
long long dp[NMAX + 5];

struct cmp
{
    bool operator()(edge e1, edge e2)
    {
        return e1.cost > e2.cost;
    }
};

priority_queue <edge, vector <edge>, cmp> pq;

void dijkstra(int node)
{
    edge e;
    e.dest = 1;
    e.cost = 0;
    dp[node] = 0;

    pq.push(e);

    while(!pq.empty())
    {
        edge e = pq.top();
        pq.pop();

        for(auto neigh : graph[e.dest])
        {
            if(dp[neigh.dest] == -1 or dp[neigh.dest] > dp[e.dest] + neigh.cost)
            {
                dp[neigh.dest] = dp[e.dest] + neigh.cost;

                edge new_edge;
                new_edge.dest = neigh.dest;
                new_edge.cost = dp[neigh.dest];

                pq.push(new_edge);
            }
        }
    }
}

int main()
{
    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;

        edge e;
        e.dest = b;
        e.cost = c;
        graph[a].push_back(e);
    }

    for(int i = 1; i <= n; i++)
        dp[i] = -1;

    dijkstra(1);

    for(int i = 2; i <= n; i++)
        if(dp[i] == -1)
        dp[i] = 0;

    for(int i = 2; i <= n; i++)
        fout << dp[i] << ' ';

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