#include <iostream>
//#include <fstream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
//ifstream si("dijkstra.in");
//ofstream so("dijkstra.out");
FILE*si=fopen("dijkstra.in","r");
FILE*so=fopen("dijkstra.out","w");
const int NMAX=50005;

struct muchie
{
    int pct,c;
    bool operator <(const muchie &var) const
    {
        return c>var.c;
    }
};
vector<muchie> v[NMAX];
int d[NMAX];
priority_queue<muchie> x;
const int INF=1000000000;
int main()
{
    int n,m;
    //si>>n>>m;
    fscanf(si,"%i %i",&n,&m);
    int a,b,c,i;
    for(i=0;i<m;++i)
    {
        fscanf(si,"%i %i %i",&a,&b,&c);
        v[a].push_back({b,c});
    }
    for(i=2;i<=n;++i)
        d[i]=INF;
    d[1]=0;
    x.push({1,0});
    int el;
    while(!x.empty())
    {
        a=x.top().pct;
        b=x.top().c;
        x.pop();
        if(d[a]!=b)
            continue;
        el=v[a].size();
        for(i=0;i<el;++i)
        {
            if(d[v[a][i].pct]>b+v[a][i].c)
            {
                d[v[a][i].pct]=b+v[a][i].c;
                x.push({v[a][i].pct,d[v[a][i].pct]});
            }
        }
    }
    for(i=2;i<=n;++i)
    {
        if(d[i]!=INF)
            fprintf(so,"%i ",d[i]);
        else
            fprintf(so,"0 ");
    }
    fprintf(so,"\n");
    return 0;
}