#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
struct Heap_Node
{
    int dist;
    int node;
    bool operator <(const Heap_Node &other)const
    {
        return dist>other.dist;
    }
};
struct element
{
    int vecin;
    int val;
};
priority_queue<Heap_Node>heap;
vector<element>graph[50005];
int dist[50005];
void dijkstra()
{
    memset(dist,0x3F,sizeof dist);
    Heap_Node first;
    first.dist=0;
    first.node=1;
    dist[1]=0;
    heap.push(first);
    while(heap.size()>0)
    {
        int curent=heap.top().node;
        int distcurent=heap.top().dist;
        heap.pop();
        if(distcurent>dist[curent])
        {
            continue;
        }
        for(int i=0;i<graph[curent].size();i++)
        {
            element vecin=graph[curent][i];
            int distnou=dist[curent]+vecin.val;
            if(distnou<dist[vecin.vecin])
            {
                dist[vecin.vecin]=distnou;
                Heap_Node nou;
                nou.dist=distnou;
                nou.node=vecin.vecin;
                heap.push(nou);
            }
        }
    }
}
int main()
{
    int nr, n;
    cin>>nr>>n;
    for(int i=1;i<=n;i++)
    {
        int a;
        element b;
        cin>>a>>b.vecin>>b.val;
        graph[a].push_back(b);
    }
    dijkstra();
    for(int i=2;i<=nr;i++)
    {
        cout<<dist[i]<<" ";
    }
    return 0;
}