#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 2000000000

using namespace std;

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

struct muchie
{
    int x, y, c;
};

bool operator<(const muchie& a, const muchie& b)
{
    return a.c>b.c;
}

vector <muchie> Graf[400100];
priority_queue <muchie> Q;
int d[400100];
int n,m,start;
bool viz[400100];

void Dijkstra()
{
    muchie aux;
    int i;
    while(!Q.empty())
    {
        aux=Q.top();
        Q.pop();
        /*if(!viz[aux.y])
        {
            viz[aux.y]=true;
            for(i=0; i<Graf[aux.y].size(); i++)

                if(!viz[Graf[aux.y][i].y] && d[Graf[aux.y][i].y]>d[aux.x]+Graf[aux.y][i].c)
                {
                    d[Graf[aux.y][i].y]=d[aux.x]+Graf[aux.y][i].c;
                    cout<<"\naux.x="<<aux.x<<' '<<" aux.c="<<Graf[aux.y][i].c<<endl;
                    cout<<"\ndistante="<<d[aux.x]<<' '<<aux.c<<' '<<aux.c+d[aux.x]<<endl;
                    cout<<"\n d["<<Graf[aux.y][i].y<<"]="<<  d[Graf[aux.y][i].y]<<endl;
                    Q.push(Graf[aux.y][i]);
                }
                if()*/
       // if(!viz[aux.y])
        //{
          //  viz[aux.y]=true;
            for(i=0; i<Graf[aux.y].size(); i++)
                if(d[Graf[aux.y][i].y]>d[aux.y]+Graf[aux.y][i].c)
                {
                    d[Graf[aux.y][i].y]=d[aux.y]+Graf[aux.y][i].c;
                    //cout<<Graf[aux.y][i].y<<' '<<d[Graf[aux.y][i].y]<<endl;
                    Q.push(Graf[aux.y][i]);

                }
      //  }
    }

}

int main()
{

    in>>n>>m;
    start=1;
    int i,a,b,cost;
    muchie aux;
    for(i=0; i<m; i++)
    {
        in>>a>>b>>cost;
        aux.x=a;
        aux.y=b;
        aux.c=cost;
        Graf[a].push_back(aux);
       /* aux.x=b;
        aux.y=a;
        Graf[b].push_back(aux);*/
    }

    aux.x=start;
    aux.y=start;
    aux.c=0;
    Q.push(aux);

    for (i=1; i<=n; i++)
        d[i]=inf;
    d[start]=0;

    Dijkstra();

    for(i=2; i<=n; i++)
        if(d[i]!=inf)
            out<<d[i]<<' ';
        else
            out<<0<<' ';


    return 0;
}