#include<bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n; vector<pair<int,int>>graph[7501];
typedef pair<int, int> iPair;
void shortestpath(int x)
{priority_queue<iPair,vector<iPair>,greater<iPair>> pq;
vector<int> dist(n, INF);
pq.push(make_pair(0, x));
dist[x] = 0;
while (!pq.empty())
{int u = pq.top().second;
pq.pop();

for(vector< pair<int, int> >::iterator i=graph[u].begin();i!=graph[u].end();i++)
{int v = (*i).first;
int weight = (*i).second;
if (dist[v] > dist[u] + weight)
{ dist[v] = dist[u] + weight;
 pq.push(make_pair(dist[v], v)); }}}
 for (int i = 2; i <= n; ++i)
 {if(dist[i]==INF){dist[i]=0;}
 fout<<dist[i]<<' ';}}
int main()
{int e,c,u,v; fin>>n>>e;
for(int i=0;i<e;i++){fin>>u>>v>>c; graph[u].push_back({v,c});}

shortestpath(1);

    return 0;
}