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

using namespace std;

fstream fin("dijkstra.in", ios::in);
fstream fout("dijkstra.out", ios::out);
#define MAXN  50005
#define INF 0x3f3f3f3f
vector <pair<int, int> > list[MAXN];
int n, dist[MAXN];

class compare{
 public:
    bool operator() (int x, int y){
        return dist[x] > dist[y];
    }
};

priority_queue< int, vector<int>, compare > heap;

void read()
{
    int x, y, m, c;
    fin >> n >> m;
    for(int i=1; i<=m; i++)
        fin >> x >> y >> c,
        list[x].push_back(make_pair(y, c));
}
void dijkstra(int start)
{
    for(int i=1; i<=n; i++)
        dist[i] = INF;
    dist[start] = 0;
    heap.push(start);

    while(!heap.empty()){
        int node = heap.top();
        heap.pop();

        for(int i=0, size = list[node].size(); i < size; i++){
            int new_node = list[node][i].first;
            if(dist[new_node] > dist[node] + list[node][i].second)
                dist[new_node] = dist[node] + list[node][i].second,
                heap.push(new_node);
        }
    }
}

int main()
{
	read();
    dijkstra(1);

    for(int i=2; i<=n; i++)
        if(dist[i] != INF) fout << dist[i] << " ";
        else fout << 0 << " ";

    fin.close();
	fout.close();
	return 0;
}