#include <fstream>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

#define Nmax 50001
const int oo = (1<<31) -1;

int N,M;
int dist[Nmax];
bool InCoada[Nmax];

struct compara{
    bool operator()(int x,int y)
    {
        return dist[x]>dist[y];
    }
};

priority_queue <int, vector <int>, compara> coada;

vector < pair <int, int> > Vecini[Nmax];

void citeste(){
   in>>N>>M;
   for(int i=1;i<=M;i++)
   {
       int x,y,c;
       in>>x>>y>>c;
       Vecini[x].push_back(make_pair(y,c));
   }
}

void afisare(){
    for(int i=2;i<=N;i++)
    {
        if(dist[i]==oo) out<<"0 ";
        else out<<dist[i]<<' ';
    }
}

void dij(int nod_plecare)
{
    for(int i=1;i<=N;i++) dist[i]=oo;

    dist[nod_plecare]=0;
    coada.push(nod_plecare);
    InCoada[nod_plecare] = 1;

    while(!coada.empty()){
        int nod_curent = coada.top();
        coada.pop();
		InCoada[nod_curent] = 0;
        int l = Vecini[nod_curent].size();
        for(int i=0;i<l;i++)
        {
             int Vecin = Vecini[nod_curent][i].first;
             int Cost = Vecini[nod_curent][i].second;
             if(dist[nod_curent] + Cost < dist[Vecin])
             {
                dist[Vecin] = dist[nod_curent] + Cost;
                if(InCoada[Vecin]==0)
                {
                   InCoada[Vecin] = 1;
                   coada.push(Vecin);
                }
             }
        }
    }
}

int main()
{
    citeste();
    dij(1);
    afisare();
    return 0;
}