using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;


static class P
{
    static void Main()
    {
        //頂点それぞれについてツアー
        //1→i→1
        //単一始点最短路を打って
        //1減る ということを
        var nm = Console.ReadLine().Split().Select(int.Parse).ToList();
        List<Tuple<int, int>>[] neighbour = Enumerable.Repeat(0, nm[0]).Select(_ => new List<Tuple<int, int>>()).ToArray();

        for (int i = 0; i < nm[1]; i++)
        {
            var abc = Console.ReadLine().Split().Select(int.Parse).ToList();
            neighbour[abc[0] - 1].Add(new Tuple<int, int>(abc[1] - 1, abc[2]));
            neighbour[abc[1] - 1].Add(new Tuple<int, int>(abc[0] - 1, abc[2]));
        }

        //0-(n-1) : 通常の点
        //n-(2*n-1) : 既にvipチケ使った点
        int[] distances = Enumerable.Repeat(-1, nm[0] * 2).ToArray();
        //PriorityQueue<Tuple<int, int>> pqueue = new PriorityQueue<Tuple<int, int>>(nm[1]);
        Heap pqueue = new Heap(nm[1] * 8);
        pqueue.Push(new Tuple<int, int>(0, 0));
        while (pqueue.Count > 0)
        {
            var item = pqueue.Pop();
            Debug.WriteLine($"{item.Item2} {item.Item1}");
            if (distances[item.Item2] >= 0) continue;
            distances[item.Item2] = item.Item1;

            if (item.Item2 >= nm[0])
            {
                foreach (var edge in neighbour[item.Item2 - nm[0]])
                {
                    pqueue.Push(new Tuple<int, int>(item.Item1 + edge.Item2, edge.Item1 + nm[0]));
                }
            }
            else
            {
                foreach (var edge in neighbour[item.Item2])
                {
                    pqueue.Push(new Tuple<int, int>(item.Item1 + edge.Item2, edge.Item1));
                    pqueue.Push(new Tuple<int, int>(item.Item1, edge.Item1 + nm[0]));
                }
            }
        }
        Console.WriteLine(string.Join("\n", distances.Zip(distances.Skip(nm[0]), (x, y) => x + Min(x, y))));
    }
}

//  Microsoft Windows Client Platform
//  Copyright (C) Microsoft Corporation. All rights reserved.
internal class PriorityQueue<T> where T : IComparable
{
    private T[] _heap;
    private const int DefaultCapacity = 6;

    public PriorityQueue(int capacity)
    {
        Count = 0;
        _heap = new T[capacity > 0 ? capacity : DefaultCapacity];
    }
    
    public int Count { get; set; }

    public T Top
    {
        get
        {
            Debug.Assert(Count > 0);
            return _heap[0];
        }
    }

    public void Push(T value)
    {
        if (Count == _heap.Length)
        {
            T[] temp = new T[Count * 2];
            for (int i = 0; i < Count; ++i)
            {
                temp[i] = _heap[i];
            }
            _heap = temp;
        }
        
        int index = Count;
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (value.CompareTo(_heap[parentIndex]) >= 0) break;
            _heap[index] = _heap[parentIndex];
            index = parentIndex;
        }

        _heap[index] = value;
        Count++;
    }
    
    public T Pop()
    {
        T top = Top;
        Debug.Assert(Count != 0);
        if (Count > 1)
        {
            int parent = 0;
            int leftChild = (parent * 2) + 1;

            while (leftChild < Count)
            {
                int rightChild = leftChild + 1;
                int bestChild = (rightChild < Count && _heap[rightChild].CompareTo(_heap[leftChild]) < 0) ? rightChild : leftChild;
                
                _heap[parent] = _heap[bestChild];

                parent = bestChild;
                leftChild = (parent * 2) + 1;
            }

            _heap[parent] = _heap[Count - 1];
        }
        Count--;
        return top;
    }
}

class Heap
{
    public int Count;
    Tuple<int, int>[] obj;
    public Heap(int maxsize)
    {
        Count = 0;
        obj = new Tuple<int, int>[maxsize];
    }
    public void Push(Tuple<int, int> a)
    {
        int i = Count;
        Count++;
        while (i > 0)
        {
            int p = (i - 1) / 2;
            if (obj[p].Item1 <= a.Item1)
            {
                obj[i] = a;
                break;
            }
            obj[i] = obj[p];
            i = p;
        }
        if (i == 0)
        {
            obj[0] = a;
        }
    }
    public Tuple<int, int> Pop()
    {
        Tuple<int, int> t = obj[0];
        int i = 0;
        Count--;
        while (2 * i + 1 < Count)
        {
            int p = 2 * i + 1;
            if (p + 1 < Count && obj[p + 1].Item1 < obj[p].Item1)
            {
                p++;
            }
            if (obj[p].Item1 < obj[Count].Item1)
            {
                obj[i] = obj[p];
                i = p;
            }
            else
            {
                obj[i] = obj[Count];
                break;
            }
        }
        if (2 * i + 1 >= Count)
        {
            obj[i] = obj[Count];
        }
        return t;
    }
}