#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin  ("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax=50005;
const int oo = (1 << 30);
int n,m,d[nmax];
bool incoada[nmax];
vector < pair <int,int> >g[nmax];
struct compara{
    bool operator()(int x, int y)
    {
        return d[x] > d[y];
    }
};
priority_queue <int, vector<int>,compara>coada;
void read()
{
    int a,b,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
    }
}
void dijkstra(int nodstart)
{
    for(int i =1;i<=n;i++)
        d[i]=oo;
    d[nodstart]=0;
    coada.push(nodstart);
    incoada[nodstart]=1;
    while(!coada.empty())
    {
        int nodcurent=coada.top();
        coada.pop();
        incoada[nodcurent]=0;
        for(unsigned int i=0;i<g[nodcurent].size();i++)
        {
             int vecin = g[nodcurent][i].first;
            int cost =g[nodcurent][i].second;
            if(d[nodcurent]+ cost < d[vecin])
            {
                d[vecin]=d[nodcurent]+ cost;
                if(incoada[vecin]== 0)
                {
                    coada.push(vecin);
                    incoada[vecin]=1;
                }
            }

        }
    }
}
void print()
{
    for(int i =2;i<=n;i++)
    {
        if(d[i]==oo)
            fout<<'0'<<' ';
        else
            fout<<d[i]<<' ';
    }
}
int main()
{
    read();
    dijkstra(1);
    print();
return 0;
}