#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

struct arc{int a; int l;};
    arc nod;

int n,m,x,y,l1,dis[50005],viz[50005];

vector <arc> gr[50005];

queue <int> coada;
void dij(int p)
{
    int i,j,z;
    coada.push(p);
    while (coada.size()!=0)
    {
        z=coada.front();
        for(i=0;i<gr[z].size();i++)
            {
                if(dis[gr[z][i].a]>dis[z]+gr[z][i].l)
                    {
                    dis[gr[z][i].a]=dis[z]+gr[z][i].l;
                    coada.push(gr[z][i].a);
                    }
            }
        coada.pop();
    }

}


int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>l1;
        nod.a=y;
        nod.l=l1;
        gr[x].push_back(nod);

    }
    for(i=1;i<=n;i++)
        dis[i]=50005;
    dis[1]=0;
    dij(1);
    for(i=2;i<=n;i++)
        g<<dis[i]<<" ";
    return 0;
}