#include <fstream>
#include <limits.h>
#include <vector>
#include <queue>
#include <string.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, k;
int dist[nMax], poz[nMax], heap[nMax];
vector<pair<int, int> > G[nMax];
void read()
{
    int a, b, c;
    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].pb(mkp(b, c));
    }
}
void upDate(int pozi)
{
    int po;
    while(pozi/2)
    {
        po=pozi/2;
        if(dist[heap[po]]>dist[heap[pozi]])
        {
            swap(heap[po], heap[pozi]);
            swap(poz[heap[po]], poz[heap[pozi]]);
            pozi=po;
        }
        else
            break;
    }
}
void downDate(int pozi)
{
    int po;
    while(pozi*2<=k)
    {
        po=pozi*2;
        if(po+1<=k && dist[heap[po]]>dist[heap[po+1]])
            po++;

        if(dist[heap[pozi]]>dist[heap[po]])
        {
            swap(heap[pozi], heap[po]);
            swap(poz[heap[pozi]], poz[heap[po]]);
            pozi=po;
        }
        else
            break;
    }
}
int heap_extract(int pozi)
{
    int node=heap[pozi];
    swap(heap[pozi], heap[k]);
    swap(poz[heap[pozi]], poz[heap[k]]);
    k--;
    downDate(pozi);

    return node;
}
void heap_insert(int node)
{
    heap[++k]=node;
    poz[node]=k;
}
void solve()
{
    int S=1;
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    dist[S]=0;
    heap_insert(S);

    while(k)
    {
        int node=heap_extract(1);

        for(vector<pair<int, int> >::iterator it=G[node].begin();it!=G[node].end();it++)
        {
            int fiu=it->first;
            int dst=it->second;

            if(dist[node]+dst<dist[fiu])
            {
                dist[fiu]=dist[node]+dst;
                if(poz[fiu]==0)
                    heap_insert(fiu);
                upDate(poz[fiu]);
            }
        }
    }
}
void write()
{
    for(int i=2;i<=n;i++)
        fout<<(dist[i]!=INF ? dist[i] : 0)<<" ";
}
int main()
{
    read();
    solve();
    write();
    return 0;
}