#include <fstream>
#include <iostream>

#include <vector>
#include <set>

using namespace std;

const unsigned int INFINITY = (1 << 31);

class HeapElement
{
private:
    unsigned int Key;
    unsigned int Data;
public:
    HeapElement() : Key(0) , Data(0)
    {
    }
    HeapElement(const unsigned int& _Key, const unsigned int& _Data) : Key(_Key) , Data(_Data)
    {
    }

    unsigned int GetKey()
    {
        return Key;
    }
    void SetKey(const unsigned int& _Key)
    {
        Key = _Key;
    }
    unsigned int GetData()
    {
        return Data;
    }
    void SetData(const unsigned int& _Data)
    {
        Data = _Data;
    }
};

class Heap
{
private:
    vector < HeapElement > Elements;
    unsigned int CurrentElement;

    public:
        Heap(unsigned int Size) : Elements(Size + 5) , CurrentElement(1)
        {
        }

        void ReheapDown(unsigned int Root, unsigned int Bottom)
        {
            unsigned int MinChild;
            unsigned int RightChild;
            unsigned int LeftChild;

            LeftChild = Root * 2;
            RightChild = Root * 2 + 1;

            if(LeftChild <= Bottom)
            {
                if(LeftChild == Bottom)
                {
                    MinChild = LeftChild;
                }
                else
                {
                    if(Elements[LeftChild].GetKey() <= Elements[RightChild].GetKey())
                    {
                        MinChild = LeftChild;
                    }
                    else
                    {
                        MinChild = RightChild;
                    }
                }

                if(Elements[Root].GetKey() >= Elements[MinChild].GetKey())
                {
                    swap(Elements[Root], Elements[MinChild]);
                    ReheapDown(MinChild, Bottom);
                }
            }
        }
        void ReheapUp(unsigned int Root, unsigned int Bottom)
        {
            unsigned int Parent;

            if(Bottom > Root)
            {
                Parent = Bottom / 2;
                if(Elements[Parent].GetKey() >= Elements[Bottom].GetKey())
                {
                    swap(Elements[Parent], Elements[Bottom]);
                    ReheapUp(Root, Parent);
                }
            }
        }

        void Enqueue(unsigned int Key, unsigned int Data)
        {
            Elements[CurrentElement].SetKey(Key);
            Elements[CurrentElement].SetData(Data);
            ReheapUp(1, CurrentElement);
            CurrentElement++;
        }
        HeapElement Dequeue()
        {
            HeapElement Item(Elements[1].GetKey(), Elements[1].GetData());
            CurrentElement--;
            Elements[1] = Elements[CurrentElement];
            ReheapDown(1 , CurrentElement - 1);

            return Item;
        }
        unsigned int CurrentElements()
        {
            return CurrentElement - 1;
        }

        void ChangeKey(unsigned int Data, unsigned int Key)
        {
            unsigned int i;
            for(i = 1 ; i < CurrentElement ; ++i)
                if(Elements[i].GetData() == Data)
                {
                    Elements[i].SetKey(Key);
                    if(Elements[i].GetKey() < Elements[i/2].GetKey())
                        ReheapUp(1, i);
                    else
                        if(Elements[i].GetKey() > Elements[i*2].GetKey() || Elements[i].GetKey() > Elements[i*2+1].GetKey())
                            ReheapDown(1, i);

                    return;
                }
        }
};

class UnorientedGraph
{
private:
    const unsigned int Nodes, Edges;
    vector < vector < unsigned int > > AdjacencyMatrix;

public:
    UnorientedGraph(const unsigned int& _Nodes,const unsigned int& _Edges) : Nodes(_Nodes), Edges(_Edges)
    {
        unsigned int i;
        for(i = 0 ; i <= Nodes ; ++i)
            AdjacencyMatrix.push_back(vector < unsigned int > (Nodes + 1));
    }

    void AddEdge(const unsigned int& NodeA, const unsigned int& NodeB, const unsigned int& Cost)
    {
        AdjacencyMatrix[NodeA][NodeB] = Cost;
        AdjacencyMatrix[NodeB][NodeA] = Cost;
    }

    void Djikstra(const unsigned int& StartNode)
    {
        unsigned int i;

        vector < unsigned int > DistanceVector (Nodes + 1, INFINITY);
        DistanceVector[StartNode] = 0;

        vector < bool > VisitedVector (Nodes + 1, false);

        unsigned int CurrentNode, Distance;

        Heap PQueue(Nodes);
        for(i = 1 ; i <= Nodes ; ++i)
            PQueue.Enqueue(DistanceVector[i], i);

        while(PQueue.CurrentElements())
        {
            CurrentNode = PQueue.Dequeue().GetData();
            VisitedVector[CurrentNode] = true;

            for(i = 1 ; i <= Nodes ; ++i)
                if(AdjacencyMatrix[CurrentNode][i] && !VisitedVector[i])
                {
                    Distance = DistanceVector[CurrentNode] + AdjacencyMatrix[CurrentNode][i];
                    if(Distance < DistanceVector[i])
                    {
                        DistanceVector[i] = Distance;
                        PQueue.ChangeKey(i , Distance);
                    }
                }
        }

        return;
    }
};

int main()
{
    fstream fin("dijkstra.in", fstream::in);
    fstream fout("dijkstra.out", fstream::out);

    int Nodes, Edges;
    fin >> Nodes >> Edges;

    UnorientedGraph Graph(Nodes, Edges);

    int NodeA, NodeB, Distance;
    for(int i = 1 ; i <= Edges ; ++i)
    {
        fin >> NodeA >> NodeB >> Distance;
        Graph.AddEdge(NodeA, NodeB, Distance);
    }

    Graph.Djikstra(1);

    return 0;
}