#include <fstream>
#include <vector>

#define INF 50001

using namespace std;

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

struct arc
{
    int nod, cost;
};
struct nod
{
    int dist, ind;
};
vector<arc> vec[50001];
int n,d[50001],t[50001],h[50001],cn;


void up(int ind)
{
    if(ind>1)
    {
        if(d[h[ind]]<d[h[ind/2]])
        {
            swap(h[ind],h[ind/2]);
            up(ind/2);
        }
    }
}
void down(int ind)
{
    if(ind<cn)
    {
        if(((d[h[ind]]>d[h[2*ind]])&&(2*ind<=cn))||((d[h[ind]]>d[h[2*ind+1]])&&(2*ind+1<=cn)))
        {
            if(d[h[2*ind]]<d[h[2*ind+1]])
            {
                swap(h[ind],h[2*ind]);
                down(2*ind);
            }
            else
            {
                swap(h[ind],h[2*ind+1]);
                down(2*ind+1);
            }
        }
    }
}
int main()
{
    int m,x;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x;
        arc aux;
        fin>>aux.nod>>aux.cost;
        vec[x].push_back(aux);
    }
    for(int i=1; i<=n; i++)
        d[i]=INF;
    d[1]=0;
    for(int i=1; i<=n; i++)
        h[i]=i;
    for(int i=0; i<vec[1].size(); i++)
    {
        d[vec[1][i].nod]=vec[1][i].cost;
        t[vec[1][i].nod]=1;
    }
    cn=n;
    h[1]=h[cn];
    cn--;
    if(cn>0) down(1);
    for(int pas=1; pas<n; pas++)
    {
        int Min=INF;
        int vf=h[1];
        h[1]=h[cn];
        cn--;
        if(cn>0) down(1);
        int l=vec[vf].size();
        for(int j=0; j<l; j++)
        {
            if(d[vec[vf][j].nod]>d[vf]+vec[vf][j].cost)
            {
                d[vec[vf][j].nod]=d[vf]+vec[vf][j].cost;
                t[vec[vf][j].nod]=vf;
            }
        }
    }
    for(int i=2; i<=n; i++)
        if(d[i]==INF)
            fout<<0<<" ";
        else fout<<d[i]<<" ";
    return 0;
}