#include<fstream>
#include<vector>
#include<queue>

#define inf 100001

using namespace std;

vector<pair<int, int> > *graph;
vector<int> distances;
queue <int> q;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


int n, m, u,v,cost, current;

void dijkstra(int vertex)
{
    distances[vertex] = 0;
    q.push(vertex);
    while(!q.empty())
    {
        current = q.front(); q.pop();
        for(unsigned int i=0; i<graph[current].size(); i++)
        {
            if(distances[current] + graph[current][i].second < distances[graph[current][i].first])
            {
                distances[graph[current][i].first] = distances[current] + graph[current][i].second;
                q.push(graph[current][i].first);
            }
        }
    }
}

int main()
{

    fin>>n>>m;
    graph = new vector<pair<int, int> > [n];
    for(int i=0; i<n; i++) {distances.push_back(inf);}

    for(int i=0; i<m; i++)
    {
        fin>>u>>v>>cost;
        u--; v--;
        graph[u].push_back(make_pair(v,cost));
    }

    dijkstra(0);

    for(int i = 1; i<n; i++)
        if(distances[i]==inf) fout<<0<<" ";
        else fout<<distances[i]<<" ";

    return 0;
}