#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

#define INF 0x3f3f3f3f

int N,M;

int VIZ[50005],dist[50005];

vector<pair<int,int> > A[50005];

struct cmp
{
    bool operator()(int a,int b)
    {
        return dist[a]>dist[b];
    }
};

priority_queue <int,vector<int>,cmp> PQ;

int main()
{
    fin >> N >> M;
    int i;
    for (i=1;i<=M;++i)
    {
        int a,b,cost;
        fin >> a >> b >> cost;
        A[a].push_back({b,cost});
    }
    for (i=2;i<=N;++i)
    {
        dist[i]=INF;
    }
    PQ.push(1);
    VIZ[1]=1;
    while (!PQ.empty())
    {
        int cur=PQ.top();
        PQ.pop();
        VIZ[cur]=0;
        vector <pair<int,int> > :: iterator it;
        for (it=A[cur].begin();it!=A[cur].end();++it)
        {
            int val=(*it).first;
            int cost=(*it).second;
            if (dist[cur]+cost<dist[val])
            {
                dist[val]=dist[cur]+cost;
                if (VIZ[val]==0)
                {
                    VIZ[val]=1;
                    PQ.push(val);
                }
            }
        }
    }
    for (i=2;i<=N;++i)
    {
        if (dist[i]!=INF)
        {
            fout << dist[i] << " ";
        }
        else
        {
            fout << 0 << " ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}