#include <fstream>
#include <vector>
#include <list>
#include <climits>

#define NODE(n) (n>>10)
#define COST(n) (n&1023)

/** ======================================================================= **/
class base_heap
{
protected:

    typedef std::vector<int> Vektor;
    typedef Vektor::iterator Iterator;
    typedef Vektor::const_iterator cIterator;
    Vektor x;

    inline unsigned int Left(unsigned int);
    inline unsigned int Right(unsigned int);
    inline unsigned int Parent(unsigned int);

    inline virtual void up(unsigned int)=0;
    inline virtual void down(unsigned int)=0;

public:

    base_heap();
    base_heap(unsigned int);

    void resize(unsigned int);
    void build_heap(const Vektor&);

    void push(int);
    int pop();
    unsigned int size();
    inline unsigned int get_first();

    friend std::ostream& operator<< (std::ostream&, const base_heap&);
};

inline unsigned int base_heap::Left(unsigned int node) {return node+node;}
inline unsigned int base_heap::Right(unsigned int node) {return node+node+1;}
inline unsigned int base_heap::Parent(unsigned int node) {return node/2;}

base_heap::base_heap(): x(1) {}
base_heap::base_heap(unsigned int sz): x(sz+1) {}

void base_heap::resize(unsigned int sz) {x.resize(sz+1);}
void base_heap::build_heap(const Vektor& temp)
{
    int t = x[0];
    x.clear(); x.push_back(t);
    x.insert(x.end(), temp.begin(), temp.end());

    for (unsigned int i=(x.size()-1)/2; i; i--) down(i);
}

void base_heap::push(int nr)
{
    x.push_back(nr);
    up(x.size()-1);
}
int base_heap::pop()
{
    int first = x[1];
    x[1] = x.back();
    down(1);
    x.pop_back();
    return first;
}
unsigned int base_heap::size() {return x.size()-1;}
inline unsigned int base_heap::get_first() {return x[1];}

std::ostream& operator<< (std::ostream& out, const base_heap& h)
{
    for (base_heap::cIterator i=h.x.begin()+1; i<h.x.end(); i++) {
        out << *i << " ";
    }
    out << "\n";
    return out;
}


class MaxHeap: public base_heap
{
private:

    inline void up(unsigned int);
    inline void down(unsigned int);

public:

    MaxHeap();
    MaxHeap(unsigned int);
};

MaxHeap::MaxHeap() {x[0] = INT_MAX;};
MaxHeap::MaxHeap(unsigned int sz):base_heap(sz) {x[0] = INT_MAX;};

inline void MaxHeap::up(unsigned int node)
{
    while (x[node] > x[Parent(node)]) {
        std::swap(x[node], x[Parent(node)]);
        node = Parent(node);
    }
}
inline void MaxHeap::down(unsigned int node)
{
    while (node+node <= x.size()-1) {
        if (x[Left(node)] > x[node]) {
            node = Left(node);
            if (x[node+1] > x[node]) {
                node = node+1;
            }
            std::swap(x[node], x[Parent(node)]);
        }
        else if (x[Right(node)] > x[node]) {
            node = Right(node);
            std::swap(x[node], x[Parent(node)]);
        }
        else break;
    }
}


class MinHeap: public base_heap
{
private:

    inline void up(unsigned int);
    inline void down(unsigned int);

public:

    MinHeap();
    MinHeap(unsigned int);
};

MinHeap::MinHeap() {x[0] = INT_MIN;}
MinHeap::MinHeap(unsigned int sz):base_heap(sz) {x[0] = INT_MIN;}

inline void MinHeap::up(unsigned int node)
{
    while (x[node] < x[Parent(node)]) {
        std::swap(x[node], x[Parent(node)]);
        node = Parent(node);
    }
}
inline void MinHeap::down(unsigned int node)
{
    while (node+node <= x.size()-1) {
        if (x[Left(node)] < x[node]) {
            node = Left(node);
            if (x[node+1] < x[node] && node+1 < x.size()) {
                node = node+1;
            }
            std::swap(x[node], x[Parent(node)]);
        }
        else if (x[Right(node)] < x[node] && Right(node) < x.size()) {
            node = Right(node);
            std::swap(x[node], x[Parent(node)]);
        }
        else break;
    }
}


typedef base_heap* Heap;
/** ======================================================================= **/

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

int n, m;
std::vector< std::list<int> > x;
std::vector<int> path;

void dijkstra (int node)
{
    path[node] = 0;
    Heap Min = new MinHeap;
    Min->push (node);

    int pos, newlen;
    std::list<int>::iterator i;
    while (Min->size()) {
        pos = Min->pop();
        for (i=x[pos].begin(); i!=x[pos].end(); i++) {
            newlen = path[pos] + COST(*i);
            if (newlen < path[NODE(*i)]) {
                path[NODE(*i)] = newlen;
                Min->push (NODE(*i));
            }
        }
    }
}

int main()
{
    in >> n >> m;
    x.resize (n+1);
    path.resize (n+1, INT_MAX);

    int a, b, c, i;
    for (i=0; i<m; i++) {
        in >> a >> b >> c;
        x[a].push_back ((b << 10) + c);
    }

    dijkstra (1);

    for (i=2; i<=n; i++) out << path[i] << " ";
}