#include <bits/stdc++.h>
using namespace std;

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

int n, m;

struct elem
{
    int node, cost;

    bool operator < (const elem other) const
    {
        return cost > other.cost;
    }
};

vector <elem> v[50005];

priority_queue <elem> pq;

int dist[50005];

void dijkstra(int p)
{
    for(int i = 1; i <= n; i ++)
        dist[i] = INT_MAX;

    pq.push({p,0});

    while(!pq.empty())
    {
        int currnode = pq.top().node;
        int currdist = pq.top().cost;

        pq.pop();

        if(dist[currnode] == INT_MAX)
        {

            dist[currnode] = currdist;

            for(auto it : v[currnode])
            if(dist[it.node] == INT_MAX)
                pq.push({it.node,currdist + it.cost});
        }
    }
}

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

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

        fin >> x >> y >> z;

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

    dijkstra(1);

    for(int i = 2; i <= n; i ++)
        if(dist[i] == INT_MAX)
        fout << 0 << " ";
    else
        fout << dist[i] << " ";
    return 0;
}