#include <iostream>
#include<fstream>
#include<queue>
#include <limits.h>
#define noduri 50001
#define muchii 250001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int d[noduri];
struct vecin
{
    int v, cost;
};
class ComparisonClass {
    public:
    bool operator() (int Node1,int Node2) {
        if(d[Node1]>d[Node2])
            return true;
        return false;
    }
};
int main()
{
    int n;
    f>>n;
    int m;
    f>>m;
    vector<vecin>* la;
    la= new vector<vecin> [n+1];
    int x;
    vecin y;

    for(int i =1; i<=m; i++)
    {
        f>>x;
        f>>y.v>>y.cost;
        la[x].push_back(y);
    }
    int s=1;
    priority_queue <int, vector<int>, ComparisonClass> PQ;
    for(int i=0; i<=n; i++) //iau de la i=0 ca sa nu am probleme cu el de pe poz. 0 la construirea si repararea heap-ului
        d[i]=INT_MAX;
    //  int tata[noduri];
    //  for(int i=0;i<=n;i++)
    //    tata[i]=0;
    int Scoase[noduri];
    for(int i=1;i<=n;i++)
        Scoase[i]=0;
    d[s] = 0;
    PQ.push(s);
    int u,v;
    while(PQ.size()!=0)
    {
        u=PQ.top();
        PQ.pop();
        if(Scoase[u]==1)
            continue;
        Scoase[u]=1;
        for(int i=0; i<(int)la[u].size(); i++)
        {
            v = la[u][i].v;
            if(d[u]+la[u][i].cost < d[v])
            {
                d[v]=d[u]+la[u][i].cost;
                PQ.push(v);
                //  tata[v]=u;
            }
        }
    }

    for(int i=2; i<=n; i++)
    {
        g<<d[i]<<" ";
    }
    f.close();
    return 0;
}