import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


class Pair<U,V>{
    public U first;
    public V second;


    Pair(U first,V second) {
        this.first = first;
        this.second=second;

    }

    public static <U,V> Pair<U,V> of(U a, V b){
        return new Pair<>(a,b);
    }
}

class MinHeap {
    private int[][] Heap;
    private int size;
    private int maxsize;

    private static final int FRONT = 1;

    public MinHeap(int maxsize)
    {
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new int[2][this.maxsize + 1];
        Heap[0][0] = Integer.MIN_VALUE;
    }

    public int getSize(){
        return size;
    }

    // Function to return the position of
    // the parent for the node currently
    // at pos
    private int parent(int pos)
    {
        return pos / 2;
    }

    // Function to return the position of the
    // left child for the node currently at pos
    private int leftChild(int pos)
    {
        return (2 * pos);
    }

    // Function to return the position of
    // the right child for the node currently
    // at pos
    private int rightChild(int pos)
    {
        return (2 * pos) + 1;
    }

    // Function that returns true if the passed
    // node is a leaf node
    private boolean isLeaf(int pos)
    {
        if (pos >= (size / 2) && pos <= size) {
            return true;
        }
        return false;
    }

    // Function to swap two nodes of the heap
    private void swap(int fpos, int spos)
    {
        int tmp1,tmp2;
        tmp1 = Heap[0][fpos];
        tmp2 = Heap[1][fpos];
        Heap[0][fpos] = Heap[0][spos];
        Heap[0][spos] = tmp1;
        Heap[1][fpos] = Heap[1][spos];
        Heap[1][spos] = tmp2;
    }

    // Function to heapify the node at pos
    private void minHeapify(int pos)
    {

        // If the node is a non-leaf node and greater
        // than any of its child
        if (!isLeaf(pos) && size>0) {
            if (Heap[0][pos] > Heap[0][leftChild(pos)]
                    || Heap[0][pos] > Heap[0][rightChild(pos)]) {

                // Swap with the left child and heapify
                // the left child
                if (Heap[0][leftChild(pos)] < Heap[0][rightChild(pos)]) {
                    swap(pos, leftChild(pos));
                    minHeapify(leftChild(pos));
                }

                // Swap with the right child and heapify
                // the right child
                else {
                    swap(pos, rightChild(pos));
                    minHeapify(rightChild(pos));
                }
            }
        }
    }

    // Function to insert a node into the heap
    public void insert(Pair<Integer,Integer> element)
    {
        if (size >= maxsize) {
            return;
        }
        Heap[0][++size] = element.first;
        Heap[1][size]=element.second;
        int current = size;

        while (Heap[0][current] < Heap[0][parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    // Function to print the contents of the heap
    public void print()
    {
        for (int i = 1; i <= size / 2; i++) {
            System.out.print(" PARENT : " + Heap[0][i]
                    + " LEFT CHILD : " + Heap[0][2 * i]
                    + " RIGHT CHILD :" + Heap[0][2 * i + 1]);
            System.out.println();
        }
    }

    // Function to build the min heap using
    // the minHeapify
    public void minHeap()
    {
        for (int pos = (size / 2); pos >= 1; pos--) {
            minHeapify(pos);
        }
    }

    // Function to remove and return the minimum
    // element from the heap
    public Pair<Integer,Integer> remove()
    {
        int popped1 = Heap[0][FRONT];
        int popped2 = Heap[1][FRONT];
        Heap[0][FRONT] = Heap[0][size--];
        Heap[1][FRONT]=Heap[1][size+1];
        minHeapify(FRONT);
        return Pair.of(popped1,popped2);
    }

}

class Graf{
    private int n,m,kezd;
    private List<Pair<Integer,Integer>> szomszedok[];
    private int[] tavolsag,ut;

    /**
     * belvassuk a csomopontok szamat, elek szamat es a kezdopontot
     * inicializaljuk a tavolsag es az ut tombot
     * felepitjuk a szomszedok nevu szomszedsagi listat
     * @param sc fajlbol valo olvasashoz szukszeges
     */
    Graf(Scanner sc){
        n=sc.nextInt();
        m=sc.nextInt();
       // kezd=sc.nextInt();
        kezd=1;

        szomszedok = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            szomszedok[i]= new ArrayList<Pair<Integer,Integer>>();
        }

        ut=new int[n+1];
        tavolsag=new int[n+1];
        for(int i=0;i<=n;i++){
            tavolsag[i]=Integer.MAX_VALUE;
            ut[i]=-1;
        }

        while(sc.hasNext()){
            int p=sc.nextInt();
            int q=sc.nextInt();
            int r=sc.nextInt();
            szomszedok[p].add(Pair.of(q,r));
        }
    }

    public void Dijkstra(){
        tavolsag[kezd]=0;
        //PriorityQueue<Pair<Integer,Integer>> pQueue = new PriorityQueue<Pair<Integer,Integer>>();
        MinHeap pQueue = new MinHeap(n+1);
        pQueue.insert(Pair.of(tavolsag[kezd],kezd));
        while(pQueue.getSize()!=0){
            Pair<Integer,Integer> teteje;
            teteje=pQueue.remove();
            int distance=teteje.first;
            int csomopont=teteje.second;
            if(distance!=tavolsag[csomopont]) continue;
            for(Pair<Integer,Integer> csp : szomszedok[csomopont]){
                int newdistance = csp.second;
                int newcsomopont=csp.first;
                if(tavolsag[newcsomopont]>distance+newdistance){
                    tavolsag[newcsomopont]=distance+newdistance;
                    ut[newcsomopont]=csomopont;
                    pQueue.insert(Pair.of(newdistance+distance,newcsomopont));
                }
            }
        }
    }

    public void kiirTav(PrintWriter pwriter){
        for(int i=2;i<=n;i++){
            if(tavolsag[i]!=Integer.MAX_VALUE) System.out.print(tavolsag[i]+" ");
            else System.out.print(0+" ");
        }
    }

}

public class geim1916_L3_2 {
    public static void main(String [] args) throws IOException {
     /*   File file = new File("geim1916_L3_2.in");
        Scanner sc = new Scanner(file);
        FileWriter fwriter = new FileWriter("geim1916_L3_2.out");
        PrintWriter pwriter = new PrintWriter(fwriter);  */
        File file = new File("dijkstra.in");
        Scanner sc = new Scanner(file);
        FileWriter fwriter = new FileWriter("dijkstra.out");
        PrintWriter pwriter = new PrintWriter(fwriter);  

        Graf A = new Graf(sc);
        A.Dijkstra();
        A.kiirTav(pwriter);

        sc.close();
        fwriter.close();
        pwriter.close();
    }
}