#include <fstream>
#include <queue>
#include <vector>
#define inf (999999999)
using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
int cst[50003],n,m;
bool viz[50003];
vector <int> v[50003];
vector <int> co[50003];
struct nazac
{
    int x;
};
bool operator<(nazac a, nazac b)
{
    if(cst[a.x]>cst[b.x])
        return true;
    return false;
}
priority_queue <nazac> q;
void citire ()
{
    int i,a,b,c;
    in>>n>>m;
    cst[1]=0;
    for(i=2;i<=n;++i)
        cst[i]=inf;
    for(i=1;i<=m;++i)
    {
        in>>a>>b>>c;
        v[a].push_back(b);
        co[a].push_back(c);
    }
}
void dijkstra ()
{
    int nc,nn,i;
    q.push({1});
    viz[1]=1;
    while(!q.empty())
    {
        nc=q.top().x;
        q.pop();
        viz[nc]=0;
        for(i=0;i<v[nc].size();++i)
        {
            nn=v[nc][i];
            if(cst[nn]>cst[nc]+co[nc][i])
            {
                cst[nn]=cst[nc]+co[nc][i];
                if(!viz[nn])
                {
                    q.push({nn});
                    viz[nn]=1;
                }
            }
        }
    }
}
int main()
{
    citire();
    dijkstra();
    for(int i=2;i<=n;++i)
    {
        if(cst[i]!=inf)
            out<<cst[i]<<' ';
        else
            out<<0<<' ';
    }
    return 0;
}