#include <fstream>
#include <vector>
#define NMAX 50004
#define INF 1000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct varf {int x, c;};
int n, x0=1, m;
vector<varf> G[NMAX];
bool uz[NMAX];
int H[NMAX];///retin varfurile organizate ca un heap dupa cmin
int cmin[NMAX];
int nr;
int poz[NMAX];
///poz[x]

void upgrade(int H[], int n, int poz);
int extrage_min(int H[],int &n);
void combinare(int H[],int n, int poz);
void inserare(int H[], int &n, int x);
void citire();
void dijkstra();
void afisare();

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}
void citire()
{
    int i, j, c;
    varf aux;
    fin>>n>>m;
    while(fin>>i>>j>>c)
    {
        ///in lista de adiacenta a lui i  trb sa adaug perechea (j, c)
        aux.x=j;
        aux.c=c;
        G[i].push_back(aux);
    }
    for(i=1; i<=n; i++)
        cmin[i]=INF;
    cmin[x0]=0;
    H[1]=x0;
    nr=1; poz[x0]=1;
}

void dijkstra()
{
    int i, j, x, cost, vfmin;
    for(i=1; i<=n; i++)
    {
        ///calculez vfmin
        vfmin=extrage_min(H, nr);
        if(cmin[vfmin]==INF)
            return;
        ///selectez vfmin
        uz[vfmin]=1;
        ///optimizez eventual costurile minime
        for(j=0; j<G[vfmin].size(); j++)
        {
            x=G[vfmin][j].x;
            cost=G[vfmin][j].c;
         if(!uz[x] && cmin[x]>cost+cmin[vfmin])
        {
            cmin[x]=cost+cmin[vfmin];
            if(poz[x]!=0)
                upgrade(H, nr, poz[x]);
               else
                inserare(H, nr, x);
        }
        }
    }
}
void afisare()
{
    int i, j;
    for(i=2; i<=n; i++)
        if(cmin[i]==INF)
            fout<<0<<' ';
           else
            fout<<cmin[i]<<' ';
}
void inserare(int H[], int &n, int x)
{
    int fiu, tata;
    fiu=n+1;
    tata=fiu/2;
    while(tata && cmin[H[tata]]>cmin[x])
    {
        H[fiu]=H[tata];
        poz[H[tata]]=fiu;
        fiu=tata;
        tata=fiu/2;
    }
    H[fiu]=x;
    n++;
    poz[x]=fiu;
}
void combinare(int H[],int n, int ppoz)
///combin H[poz] cu heapurile corecte cu radacinile pe pozitiile 2*poz si 2*poz+1
{
    int x=H[ppoz],fiu,tata;
    tata=ppoz;
    fiu=2*tata;
    while(fiu<=n)
    {
        if(fiu+1<=n&& cmin[H[fiu+1]]<cmin[H[fiu]])
            fiu++;
        if(cmin[H[fiu]]>=cmin[x])
            break;
        H[tata]=H[fiu];
        poz[H[fiu]]=tata;
        tata=fiu;
        fiu=2*tata;
    }
    H[tata]=x;
    poz[x]=tata;
}
int extrage_min(int H[],int &n)
{
    int minim=H[1];
    H[1]=H[n];
    combinare(H,n,1);
    return minim;
}
void upgrade(int H[], int n, int ppoz)
{
    int fiu=ppoz, tata=fiu/2, aux;
    while(tata)
    {
        if(H[fiu]>=H[tata])
            break;

        aux=poz[H[fiu]];
        poz[H[fiu]]=poz[H[tata]];
        poz[H[tata]]=aux;

        aux=H[fiu];
        H[fiu]=H[tata];
        H[tata]=aux;

        fiu=tata;
        tata=fiu/2;
    }
}