#include <fstream>
#include<queue>
#define inf 10000000
using namespace std;
struct muchie{
int cost, nod;
};
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 vector <muchie> g[10001];
priority_queue <pair<int,int>, vector<pair<int,int>>, greater <pair<int,int>>> q;
int n,m, d[100001], viz[100001];

int main()
{
    fin>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        g[x].push_back({c,y});
      //  g[y].push_back({c,x});
    }
    for(int i=1;i<=n;i++)
        d[i]=inf;
    d[1]=0;
    q.push({0,1});
    while(!q.empty()){

        int nod=q.top().second;
        int c=q.top().first;
        if(viz[nod]==1){
            q.pop();
            continue;
        }
        q.pop();
        viz[nod]=1;
        for(int i=0;i<g[nod].size();i++){
            int vec=g[nod][i].nod;
            int cost=g[nod][i].cost;
            if(d[vec]>d[nod]+cost){
                d[vec]=d[nod]+cost;
                q.push({d[vec],vec});
            }
        }

    }
    for(int i=2;i<=n;i++)
          if(d[i]==0)
             fout<<"0 ";
        else
            fout<<d[i]<<" ";
    return 0;
}