#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <climits>
#include <map>

struct Pair
{
    int v;
    long long weight;
    bool operator<(Pair &a)
    {
        if(weight < a.weight) return 1;
        return 0;
    }
    Pair() : v(), weight() {}
    Pair(int a, int b) : v(a), weight(b) {}
};

class Heap
{
    int *poz;
    std::vector<Pair> myV;

    void down(unsigned i)
    {
        unsigned m = i, left = 2 * i + 1, right = 2 * i + 2;
        if(myV.size() > left && myV[left] < myV[m]) m = left;
        if(myV.size() > right && myV[right] < myV[m]) m = right;
        if(m != i)
        {
            poz[myV[m].v] = i;
            poz[myV[i].v] = m;
            std::swap(myV[i], myV[m]);
            down(m);
        }
    }

    void up(unsigned i)
    {
        if(i == 0) return;
        unsigned par = (i - 1) / 2;
        if(myV[i] < myV[par])
        {
            poz[myV[par].v] = i;
            poz[myV[i].v] = par;
            std::swap(myV[i], myV[par]);
            up(par);
        }
    }


public:

    Heap(std::vector<Pair> &a) : poz(new int[a.size()]), myV(a)
    {
        for(unsigned i = 0; i < myV.size(); i++)
            poz[myV[i].v] = i;
        for(int i = myV.size() / 2; i >=0; i--)
            down(i);
    }

    bool nEmpty()
    {
        return !myV.empty();
    }

    Pair pop()
    {
        Pair aux = myV[0];
        std::swap(myV[0], myV.back());
        poz[myV[0].v] = 0;
        myV.pop_back();
        down(0);
        return aux;
    }

    void update(int vertex, int key)
    {
        myV[poz[vertex]].weight = key;
        up(poz[vertex]);
    }
};

class Graph
{
    struct Edge
    {
        int u;
        int weight;
        Edge(int a, int b) : u(a), weight(b) {}
    };

    struct Vertex
    {
        int v;
        std::vector<Edge> myV;
        Vertex() : v(), myV() {}
        Vertex(int x) : v(x), myV() {}
    };

    Vertex *Arr;
    int nV, nE;

public:

    Graph(int a, int b) : Arr(new Vertex[a]), nV(a), nE(b)
    {
        for(int i = 0; i < nV; i++)
            Arr[i] = Vertex(i);
    }

    friend std::vector<Pair> Dijkstra(const Graph &x, int source);

    friend std::istream& operator>>(std::istream& in, Graph &x)
    {
        int a, b, c;
        for(int i = 0; i < x.nE; i++)
        {
            in >> a >> b >> c;
            a--;
            b--;
            x.Arr[a].myV.push_back(Edge(b, c));
        }
        return in;
    }

    friend std::ostream& operator<<(std::ostream& out, const Graph &x)
    {
        for(int i = 0; i < x.nV; i++)
            out << x.Arr[i].myV.size() << ' ';
        return out;
    }
};

std::vector<Pair> Dijkstra(const Graph &x, int source)
{
    std::vector<Pair> myP;
    myP.resize(x.nV);
    for(int i = 0; i < x.nV; i++)
        myP[i] = Pair(i, INT_MAX);
    myP[source].weight = 0;
    Heap a(myP);
    while(a.nEmpty())
    {

        Pair aux = a.pop();

        for(unsigned i = 0; i < x.Arr[aux.v].myV.size(); i++)
        {
            long long alt = myP[aux.v].weight + x.Arr[aux.v].myV[i].weight;
            if(alt < myP[x.Arr[aux.v].myV[i].u].weight)
            {
                myP[x.Arr[aux.v].myV[i].u].weight = alt;
                a.update(x.Arr[aux.v].myV[i].u, alt);
            }
        }

    }
    return myP;
}

int main()
{
    std::ifstream in("dijkstra.in");
    std::ofstream out("dijkstra.out");

    int nV, nE;

    in >> nV >> nE;

    Graph a(nV, nE);

    in >> a;

    std::vector<Pair> b = Dijkstra(a, 0);

    for(unsigned i = 1; i < b.size(); i++)
        if(b[i].weight == INT_MAX) out << 0 << ' ';
        else out << b[i].weight << ' ';

    return 0;
}