#include <string>
#include <list>
#include <utility>
#include <fstream>

using namespace std;

class Exception {
    private:
        string message;
    public:
        Exception (string s): message (s) {}
        Exception (): message () {}
        string getMessage () {
            return message;
        }

};

class Math {
    public:
        static int integerSqrt (int val) {  // use a binary search variation
            unsigned i, pas, n (val);       // to find floor (sqrt (n)) in O(log (n)) time
            if ( val < 0 )    throw new Exception ("An exception has occured: the program was trying to extract square root from a negative number.");
            for ( pas = 1; pas * pas <= n; pas <<= 1 );
            for ( i = 0; pas; pas >>= 1 )
                if ( (i + pas) * (i + pas) <= n )
                    i += pas;
            return i;
        }
};

class MinPriorityQueue {
    private:
        int *rd, *ird, *d;
        int rad, sz, size, nn;
    private:
        int zone ( int key ) {
            int loc = key / rad;
            return loc;
        }
    public:
        MinPriorityQueue () {}
        MinPriorityQueue (int n): size (n), nn (n) {
            rad = Math::integerSqrt (n);
            sz = 1 + (n / rad);
            rd = new int [sz];
            ird = new int [sz];
            d = new int [n + 1];
            memset ( d, 63, (n + 1) * sizeof ( int ) );
            memset ( rd, 63, sz * sizeof ( int ) );
            memset ( ird, 0, sz * sizeof ( int ) );
        }
        void decreaseKey ( int key, int toVal ) {
            if ( d [key] <= toVal )     throw new Exception ("An exception has occured: the program was trying to increase the value of a key with a decrease function");
            d [key] = toVal;
            int keyLocation = zone (key);
            if (rd [keyLocation] > toVal) {
                rd [keyLocation] = toVal;
                ird [keyLocation] = key;
            }
        }
        int getValue ( int key ) {
            int v = d [ key ];
            return v;
        }
        int getMinimumValuedKey () {
            int key = 0, val = d [0];
            for (int i = 0; i < sz; ++ i) {
                if (rd [i] < val) {
                    val = rd [i];
                    key = ird [i];
                }
            }
            return key;
        }
        int getMinimumValuedKey (int zone) {
            int begin, end, key = 0, val = d [0], i;
            begin = zone * rad;
            end = begin + rad;
            for ( i = begin; i < end && i <= nn; ++ i ) {
                if ( d [i] < val ) {
                    val = d [i];
                    key = i;
                }
            }
            return key;
        }
        pair<int, int> extractMinimumValuedKey () {
            -- size;
            int key = getMinimumValuedKey ();
            int rValue = d [key];
            int keyLocation = zone (key);
            d [key] = d [0];
            int minKey = getMinimumValuedKey (keyLocation);
            ird [keyLocation] = minKey;
            rd [keyLocation] = d [minKey];
            return make_pair (key, rValue);
        }
        bool isEmpty () {
            return (size == 0);
        }
};

class Graph {
    private:
        int n, m;
        list < pair <int, int> > *adjacencyList;
        list < pair <int, int> > :: iterator *it;
    public:
        Graph () {}
        Graph (const char *fileName) {
            ifstream f (fileName);
            int x, y, z, i;
            f >> n >> m;
            adjacencyList = new list < pair <int, int> > [n + 1];
            adjacencyList [0].push_back (make_pair(-1,0));
            for ( i = 0; i < m; ++ i ) {
                f >> x >> y >> z;
                adjacencyList [x].push_back (make_pair (y, z));
            }
            f.close ();
            it = new list < pair <int, int> > :: iterator [n + 1];
            for ( i = 0; i <= n; ++ i )
                it [i] = adjacencyList [i].begin ();
        }
        int getNumberOfVertices () {
            return n;
        }
        int getNumberOfArcs () {
            return m;
        }
        pair <int, int> getNextNeighbour (int node) {
            pair <int, int> p;
            if (it [node] == adjacencyList [node].end ()) {
                it [node] = adjacencyList [node].begin ();
                p.first = -1;
            }
            else{
                p = *it [node];
                ++ it [node];
            }
            return p;
        }
};

class Dijkstra {
    private:
        Graph *graph;
        MinPriorityQueue *q;
        int *d;
        bool *u;
    private:
        void relax (int u, int v, int w) {
            int dd = d [u];
            if ( dd + w < q->getValue (v) ) {
                q->decreaseKey ( v, dd + w );
            }
        }
        void runAlgorithm () {
            pair<int, int> node;
            q->decreaseKey (1, 0);
            while ( ! q->isEmpty () ) {
                node = q->extractMinimumValuedKey ();
                u [node.first] = true;
                d [node.first] = node.second;
                pair <int, int> neighbour = graph->getNextNeighbour ( node.first );
                while ( neighbour.first != -1 ) {
                    if ( ! u [neighbour.first] )
                        relax (node.first, neighbour.first, neighbour.second);
                    neighbour = graph->getNextNeighbour ( node.first );
                }
            }
        }
    public:
        Dijkstra (const char * filename) {
            graph = new Graph (filename);
            q = new MinPriorityQueue (graph->getNumberOfVertices ());
            d = new int [1 + graph->getNumberOfVertices ()];
            u = new bool [1 + graph->getNumberOfVertices ()];
            memset (u, 0, (1 + graph->getNumberOfVertices ()) * sizeof (bool));
			memset (d, 0, (1 + graph->getNumberOfVertices ()) * sizeof (int));
            runAlgorithm ();
        }
        void printDistances (int shift, const char *filename) {
            ofstream g (filename);
            int n = graph->getNumberOfVertices ();
            for (int i = shift; i <= n; ++ i) {
					g << d [i] << ' ';
            }
            g << '\n';
            g.close ();
        }
};

class Main {
    public:
        static int main() {
            Dijkstra d ("dijkstra.in");
            d.printDistances (2, "dijkstra.out");
            return 0;
        }
};

int main () {
    return Main::main ();
}