#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define fin "dijkstra.in"
#define fou "dijkstra.out"
#define inf 100000000
using namespace std;
ifstream t1(fin);
ofstream t2(fou);
int n,m;
int d[50001];

class comp
{
public:
    bool operator()(int a,int b)
    {
        return d[a]>d[b];
    }
};

vector < pair<int,int> > g[50001];
priority_queue<int,vector<int>,comp> c;

int main()
{
    int i,j,x;
    short nod1,nod2,cost,start;
    t1>>n>>m;
    for(i=1;i<=m;i++)
    {
        t1>>nod1>>nod2>>cost;
        g[nod1].push_back(make_pair(nod2,cost));
    }
    for(i=1;i<=n;i++) d[i]=inf;
    start=1; d[start]=0;
    c.push(1);
    while(!c.empty())
    {
        x=c.top();
        c.pop();
        for(i=0;i<g[x].size();i++)
            if(d[g[x][i].first]>d[x]+g[x][i].second)
            {
                d[g[x][i].first]=d[x]+g[x][i].second;
                c.push(g[x][i].first);
            }
    }
    for(i=2;i<=n;i++) if(d[i]!=inf) t2<<d[i]<<' ';
                               else t2<<'0'<<' ';
    t1.close();
    t2.close();
    return(0);
}