#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)
{
    while(!Q.empty())
    {
        nod=Q.front();
        viz[nod]=0;

        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;
                }
            }
        }
        Q.pop();
    }

}


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;
}