#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

struct heapNode
{
    int nod, dist;
    inline bool operator < (const heapNode &other) const
    {
        return dist > other.dist;
    }
};

struct node
{
    int nod, cost;
};

int n, m, dist[50005];
vector <node> v[50005];
priority_queue <heapNode> heap;
bool used[50005];

void dijkstra()
{
    heap.push({1,0});
    while(!heap.empty())
    {
        heapNode current = heap.top();
        heap.pop();
        if(used[current.nod])
            continue;
        used[current.nod]=1;
        for(node i : v[current.nod])
            if(dist[i.nod] == 0 || dist[current.nod] + i.cost < dist[i.nod])
            {
                dist[i.nod] = dist[current.nod] + i.cost;
                heap.push({i.nod, dist[i.nod]});
            }
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        node x, y;
        fin>>x.nod>>y.nod>>y.cost;
        v[x.nod].push_back(y);
    }
    dijkstra();
    for(int i=2; i<=n; i++)
        fout<<dist[i]<<" ";
    return 0;
}