#include <bits/stdc++.h>
#define NMAX 50005
using namespace std;

/********************************************/
/// INPUT / OUTPUT

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
/********************************************/
/// GLOBAL DECLARATIONS

int N, M, nr, ans[NMAX];
bool visited[NMAX];

struct Nod
{
    int nod, dist;
} heap[2 * NMAX];

vector < Nod > muchii[NMAX];
/********************************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/********************************************/
///-------------------------------------------------------
inline void ReadInput()
{
    f >> N >> M;

    for(int i = 0 ; i < M ; ++ i)
    {
        int a, b, c;
        f >> a >> b >> c;
        muchii[a].push_back({b, c});
    }
}
///-------------------------------------------------------
void AddToHeap(int nod, int dist)
{
    nr++;

    int pos = nr;

    heap[pos].nod = nod;
    heap[pos].dist = dist;

    while(pos / 2 > 0 && heap[pos / 2].dist > heap[pos].dist)
    {
        swap(heap[pos], heap[pos / 2]);
        pos /= 2;
    }
}
///-------------------------------------------------------
void RemoveFromHeap()
{
    swap(heap[1], heap[nr]);
    nr--;

    int pos = 1;

    while(pos * 2 + 1 <= nr && (heap[pos].dist > heap[pos * 2].dist || heap[pos].dist > heap[pos * 2 + 1].dist))
    {
        if(heap[pos * 2].dist < heap[pos * 2 + 1].dist)
        {
            swap(heap[pos], heap[pos * 2]);
            pos *= 2;
        }
        else
        {
            swap(heap[pos], heap[pos * 2 + 1]);
            pos = pos * 2 + 1;
        }
    }

    if(pos == nr / 2 && heap[pos].dist > heap[nr].dist)
        swap(heap[pos], heap[nr]);
}
///-------------------------------------------------------
inline void Solution()
{
    AddToHeap(1, 0);

    while(nr > 0)
    {
        int nod = heap[1].nod;
        int dist = heap[1].dist;

        RemoveFromHeap();

        if(!visited[nod])
        {
            visited[nod] = true;
            ans[nod] = dist;

            for(auto it: muchii[nod])
            {
                if(!visited[it.nod])
                    AddToHeap(it.nod, it.dist + dist);
            }
        }
    }
}
///-------------------------------------------------------
inline void Output()
{
    for(int i = 2 ; i <= N ; ++ i)
        g << ans[i] << " ";
}
///-------------------------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}