#include <fstream>
#include <vector>
using namespace std;

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

struct DijkstraHeap {
    vector<int> v;
    vector<int> dists;
    vector<int> poz;

    DijkstraHeap(int n) : v(1, 0), dists(n+1, INT_MAX), poz(n+1, -1) {}

    void downheap(int i)
    {
        if(2*i>=v.size())
            return;

        bool isLeftMin=true;
        if(i*2+1<v.size())
        {
            if(dists[v[2*i+1]]<dists[v[2*i]])
                isLeftMin=false;
        }

        if(isLeftMin)
        {
            if(dists[v[2*i]]<dists[v[i]])
            {
                swap(v[2*i], v[i]);
                poz[v[2*i]]=2*i;
                poz[v[i]]=i;
                downheap(2*i);
            }
        }
        else
        {
            if(dists[v[2*i+1]]<dists[v[i]])
            {
                swap(v[2*i+1], v[i]);
                poz[v[2*i+1]]=2*i+1;
                poz[v[i]]=i;
                downheap(2*i+1);
            }
        }
    }

    void upheap(int i)
    {
        if(i<=1)
            return;

        if(dists[v[i]]<dists[v[i/2]])
        {
            swap(v[i], v[i/2]);
            poz[v[i]]=i;
            poz[v[i/2]]=i/2;
            upheap(i/2);
        }
    }

    void heapify() {
        for(int i=(v.size()-1)/2;i>=1;i--)
            downheap(i);
    }

    void tryUpdateDistance(int node, int distance)
    {
        if(node>=dists.size()||node<=0)
            return;

        if(distance<dists[node])
        {
            if(dists[node]==INT_MAX)
            {
                v.push_back(node);
                poz[node]=v.size()-1;
            }

            dists[node]=distance;
            upheap(poz[node]);
        }
    }

    int getMin() { return v[1]; }

    int popMin() {
        int x=v[1];
        v[1]=v[v.size()-1];
        v.pop_back();
        poz[x]=-1;
        downheap(1);
        return x;
    }

    void startAt(int node) {
        if(node>=dists.size()||node<=0)
            return;

        v.clear();
        v.push_back(0);
        for(int i=0;i<dists.size();i++)
        {
            dists[i]=INT_MAX;
            poz[i]=-1;
        }

        dists[node]=0;
        poz[node]=1;
        v.push_back(node);
    }
};


int main() {

    int n, m;
    in>>n>>m;
    vector<pair<int, int>> arcs[n+1];

    while(m)
    {
        m--;

        int a, b, c;
        in>>a>>b>>c;

        arcs[a].push_back({b, c});
    }

    DijkstraHeap dh(n);
    dh.startAt(1);

    while(dh.v.size()>1)
    {
        int x=dh.popMin();

        for(int i=0;i<arcs[x].size();i++)
        {
            int newDistance=dh.dists[x];
            if(newDistance!=INT_MAX)
                newDistance+=arcs[x][i].second;

            dh.tryUpdateDistance(arcs[x][i].first, newDistance);
        }
    }

    for(int i=2;i<dh.dists.size();i++)
        if(dh.dists[i]==INT_MAX)
            out<<0<<" ";
        else
            out<<dh.dists[i]<<" ";

    return 0;
}