#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 edge
{
    int p,c;
    bool operator <(const edge &var) const
    {
        return c>var.c;
    }
};
vector<edge> v[NMAX];
int d[NMAX];
priority_queue<edge> x;
const int INF=1000000000;
int main()
{
    int n,m;
    fscanf(si,"%i %i",&n,&m);
    int i,a,b,c;
    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});
    while(!x.empty())
    {
        a=x.top().p;
        b=x.top().c;
        x.pop();
        if(b!=d[a])
            continue;
        c=v[a].size();
        for(i=0;i<c;++i)
        {
            if(d[v[a][i].p]>b+v[a][i].c)
            {
                d[v[a][i].p]=b+v[a][i].c;
                x.push({v[a][i].p,d[v[a][i].p]});
            }
        }
    }
    for(i=2;i<=n;++i)
        if(d[i]!=INF)
            fprintf(so,"%i ",d[i]);
        else
            fprintf(so,"0 ");

    fprintf(so,"\n");
    return 0;
}