#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

typedef pair < int, int >  pii;

const int INF = 2000000000;
const int Nmax = 50001;
int N,M,V;

vector <pii> Ad[Nmax];
priority_queue <pii, vector <pii>, greater<pii> > C;
void Read()
{
    V=1;
    int x,y,d;
    fin>>N>>M;
    for(int i=1;i<=M;++i)
    {
        fin>>x>>y>>d;
        Ad[x].push_back(make_pair(y,d));
    }
}
void Dijkstra(int x)
{
    int nod,v,d;
    vector <int> dist(N,INF);
    dist[x]=0;
    C.push(make_pair(0,x));
    while(!C.empty())
    {
        nod=C.top().second;
        C.pop();
        for(int i=0;i<Ad[nod].size();++i)
        {
            v=Ad[nod][i].first;
            d=Ad[nod][i].second;
            if(dist[v] > dist[nod] + d)
            {
                dist[v]=d + dist[nod];
                C.push(make_pair(dist[v],v));
            }
        }
    }
    for(int i=2;i<=N;++i)
        fout<<dist[i]<<" ";
}
int main()
{
    Read();
    Dijkstra(V);
    return 0;
}