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

using namespace std;
#define PII pair<int,int>
#define VI vector<int>
#define pb push_back

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

const int Inf=0x3f3f3f3f;
vector<vector<PII> > G;
int n,m;
VI d;

void Read();
void Dijkstra();

int main()
{
    Read();
    Dijkstra(1,d);
    for(int i=2;i<=n;++i)
       fout<<d[i]<<" ";

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin>>n>>m;
    G.resize(n+1);
    int x,y,cost;
    while(m--)
    {
        fin>>x>>y>>cost;
        G[x].pb({y,cost});
    }

}
void Dijkstra(int nod, VI& d)
{
    int dx,y,w;
    priority_queue<PII, vector<PII>, greater<PII> > Q;
    d.resize(n+1,Inf);
    d[nod]=0;
    for(Q.push({0,nod}); !Q.empty(); Q.pop())
    {
        nod=Q.top().second, dx=Q.top().first;
        if(d[nod]<dx) continue;
        for(auto p : G[nod])
        {
            y=p.first;
            w=p.second;
            if(d[y]>d[nod]+w)
            d[y]=d[nod]+w;
            Q.push({d[y],y});
        }
    }
}