#include <iostream>
#include<fstream>
#include<queue>
#include<vector>
#define NMAX 50005

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

vector<int>G[NMAX],C[NMAX];
queue<int>Q;
int viz[NMAX];
int drum[NMAX],N,M;

void BFS(int nod)
{
    nod=Q.front();
    viz[nod]=0;
     Q.pop();
    for (unsigned int i=0;i<G[nod].size();i++)
    {
        if (drum[G[nod][i]]> drum[nod]+C[nod][i])
        {
            drum[G[nod][i]]=drum[nod]+C[nod][i];
             if (viz[G[nod][i]]==0)
             {
                 Q.push(G[nod][i]);
                 viz[G[nod][i]]=1;
             }
        }
    }

}


int main()
{
    f>>N>>M;
    int a,b,cost;
    for(int i=1;i<=M;i++)
    {
        f>>a>>b>>cost;
        G[a].push_back(b);
        C[a].push_back(cost);
    }
    Q.push(1);
    viz[1]=1;
    drum[1]=0;
    for(int i=2;i<=N;i++)
        drum[i]=500005;
    BFS(1);
    for(int i=2;i<=N;i++)
        if(drum[i]!=500005)
            g<<drum[i]<<" ";
        else
            g<<0<<" ";
    return 0;
}