/**
Infoarena
v2
alocare dinamica de memorie prin liste(smart ???)

*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define pinf 1e+38

struct lista{
        int dest;
        int cost;
        lista *urm;
        };

struct lista_d{
        int dest;
        int cost;
        int tata;
        lista_d *urm;

};
lista_d *d, *prim_d, *ult_d;

lista *N[50000];

bool viz[50000];

int n,m,i,j;
void adaugare(int i , int j,int cost)
{
lista *p;
p=new lista;
p->dest=j;
p->cost=cost;
p->urm=N[i];
N[i]=p;
}

void citire()
{int i,j,z,lung;
f>>n;
f>>m;
for(z=1;z<=m;z++)
    {
        f>>i>>j>>lung;
        adaugare(i,j,lung);
    }
}
void tipar()
{
    lista_d *d;
for(j=2;j<=n;j++)
{
d=prim_d;
while(d)
{
if(d->dest==j) g<<d->cost<<" ";
  //  cout<<"1 la "<<d->dest<<" dist="<<d->cost<<'\n';
    //cout<<d->dest<<"il are tata pe"<<d->tata<<'\n';
    d=d->urm;
}
}
}
int main()
{
citire();
///Initializam nod 1;
viz[1]=1;
lista *p;

p=N[1];
while(p)
{
    d=new lista_d;
    //d=p;
    d->cost=p->cost;
    d->dest=p->dest;
    d->tata=1;
    d->urm=NULL;
    if(prim_d==NULL) {prim_d=d;ult_d=d;}
    ult_d->urm=d;
    ult_d=d;
    p=p->urm;
}
//tipar();

int minn=pinf;

for(i=1;i<=n-1;i++)
{lista_d *poz;
    ///Cautam cea mai mica distanta nevizitata
minn=pinf;
d=prim_d;
while(d)
{
    if(minn>d->cost&&viz[d->dest]==0) {poz=d;
                                        minn=d->cost;
                                        }
    d=d->urm;
}

    ///calculamm dist prin poz
short c;
viz[poz->dest]=1;
        p=N[poz->dest];
        while(p)
        {
                lista_d *d;
                d=prim_d;
                   c=0;///consideram ca nu exista drum de la 1  la p->dest
                    while(d)
                    {
                        //cout<<d->dest<<" "<<p->dest<<'\n';
                        if(d->dest==p->dest)
                                {c=1;
                                    if(d->cost>poz->cost+p->cost) {
                                                                    d->cost=poz->cost+p->cost;
                                                                    d->tata=poz->dest;
                                                                    }
                                }
                        d=d->urm;
                    }
                if(!c) {///elementul introdus trebuie intordus in ordine dupa destinatie
                            d=new lista_d;
                            d->dest=p->dest;
                            d->cost=poz->cost+p->cost;
                            d->tata=poz->dest;
                            d->urm=NULL;
                            ult_d->urm=d;
                            ult_d=d;
                        }
            p=p->urm;
        }
}
///Vectorul distanta nu este ordonat deci afisarea ia mult timp
//si ar putea sa se ajute de niste optimizari inca din scrierea in d
tipar();

    return 0;
}