#include <fstream>
#include <vector>
#include <set>
#define NMax 50005
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int Dist[NMax],i,N,M;
bool Visited[NMax];

const int INF = 1000000005;

vector <pair <int, int> > G[NMax];

set <pair <int, int> > unvisitedNodes;

void initialize(){
    for(int i = 2; i <= N; i++){
        Dist[i] = INF, Visited[i] = false;
        unvisitedNodes.insert(make_pair(Dist[i], i));
    }

    Dist[1] = 0;
    Visited[1] = false;
    unvisitedNodes.insert(make_pair(Dist[1], 1));
}

int findMinUnvisitedNode(){
    set <pair <int, int> > :: iterator it = unvisitedNodes.begin();
    pair <int, int> minValue = (*it);
    return minValue.second;
}

void updateNeighbour(int node, int neighb, int cost){
    if(Dist[neighb] > Dist[node] + cost){
        unvisitedNodes.erase(make_pair(Dist[neighb], neighb));
        Dist[neighb] = Dist[node] + cost;
        unvisitedNodes.insert(make_pair(Dist[neighb], neighb));
    }
}

void Dijkstra(){

    initialize();

    for(int step = 1; step <= N; step++){ //O(N)
        int node = findMinUnvisitedNode(); //log(N)

        Visited[node] = true;

        unvisitedNodes.erase(unvisitedNodes.begin()); //log(N)

        for(int i = 0; i < G[node].size(); i++){ //O(M) in total
            int neighb = G[node][i].first, cost = G[node][i].second;
            updateNeighbour(node, neighb, cost); //2 * log(N)
        }
    }

    //O(Nlog(N) + Mlog(N))

    //daca M ~= N ^ 2, varianta brute e mai eficienta

    //brute: O(N ^ 2 + M)

}

int main()
{
    int a,b,c;
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    Dijkstra();
    for(i=2;i<=N;i++)
    {
        if(Dist[i]==INF)
            Dist[i]=0;
        fout<<Dist[i]<<" ";
    }

    return 0;
}