#include <fstream>
#define MAX 50010
#define infinit 100000000

using namespace std;

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

struct nod
{
    int inf,cost;
    nod *next;
};
typedef struct nod nod;
nod * sir[MAX];

int n,m,vi;
int d[MAX],viz[MAX],T[MAX];

void adauga(int a,int b,int c)
{
    nod *q=new nod;
    q->inf=a;
    q->cost=c;
    q->next=sir[b];
    sir[b]=q;
}

void citire()
{
    fin>>n>>m;
    int a,b,c;
    for (int i=0;i<m;i++)
    {
        fin>>a>>b>>c;
       // adauga(a,b,c);
        adauga(b,a,c);
    }
}

void dijkstra()
{
    memset(T,0,sizeof(T));
    memset(viz,0,sizeof(viz));
    for (int i=0;i<=n;i++)
        d[i]=infinit;
    d[vi]=0;
    viz[vi]=1;
    T[vi]=0;
    int x=n-1;
    int min=vi;
    int min1=MAX;
    while (x)
    {
        for (int i=min;i<=n;i++)
            if (viz[i])
                for (nod *r=sir[i];r;r=r->next)
                    if (d[r->inf]==infinit||(d[r->inf]>d[i]+r->cost))
                    {
                        d[r->inf]=d[i]+r->cost;
                        T[r->inf]=i;
                        if (!viz[r->inf])
                        {
                            viz[r->inf]=1;
                            x--;
                        }
                        if (i>min)
                            if (i<min1)
                                min1=i;
                    }
            min=min1;
            min1=MAX;
    }
}

void afisare()
{
    for (int i=2;i<=n;i++)
        fout<<d[i]<<" ";
    fout<<"\n";
}

int main()
{
    vi=1;
    citire();
    dijkstra();
    afisare();
    return 0;
}