#include <fstream>
#include <vector>
#include <limits.h>

#define nMax 50001
#define INF INT_MAX
#define pb push_back
#define mkp make_pair

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, nrEl;
int heap[nMax], poz[nMax], dp[nMax];
vector<pair<int, int> > G[nMax];

void downDate(int pozi)
{
    int po;
    while(pozi*2<=nrEl)
    {
        int po=pozi*2;
        if(po+1<=nrEl && dp[heap[po]]>dp[heap[po+1]])
            po++;
        if(dp[heap[pozi]]>dp[heap[po]])
        {
            swap(heap[pozi], heap[po]);
            swap(poz[heap[pozi]], poz[heap[po]]);
            pozi=po;
        }
        else
            break;
    }
}

void upDate(int pozi)
{
    int po;
    while(pozi/2)
    {
        po=pozi/2;
        if(dp[heap[pozi]]<dp[heap[po]])
        {
            swap(heap[pozi], heap[po]);
            swap(poz[heap[pozi]], poz[heap[po]]);
            pozi=po;
        }
        else
            break;
    }
}

int extractHeap(int pozi)
{
    int node=heap[pozi];
    swap(heap[pozi], heap[nrEl]);
    swap(poz[heap[pozi]], poz[heap[nrEl]]);
    nrEl--;
    downDate(1);
    return node;
}

void insertHeap(int node)
{
    heap[++nrEl]=node;
    poz[node]=nrEl;
}

void dijkstra()
{
    for(int i=2; i<=n; i++)
        dp[i]=INF;

    insertHeap(1);

    while(nrEl)
    {
        int node=extractHeap(1);
        for(vector<pair<int, int> >::iterator it=G[node].begin(); it!=G[node].end(); it++)
        {
            int fiu=it->first;
            int cost=it->second;
            if(dp[node]+cost<dp[fiu])
            {
                dp[fiu]=dp[node]+cost;
                if(poz[fiu]==0)
                    insertHeap(fiu);
                upDate(poz[fiu]);
            }
        }
    }
    for(int i=2; i<=n; i++)
        fout<<(dp[i]!=INF ? dp[i] : 0)<<" ";
}

int main()
{
    int a, b, c;
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        G[a].pb(mkp(b, c));
    }

    dijkstra();
}