#include<iostream>
#include <fstream>
#include<cstdio>
#include<vector>
#include<queue>
#define max 2000000000
using namespace std;
queue<int> Q;
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n,m;
    fin>>n>>m;
    vector<pair<int, int> >::iterator it, eit;
    vector<pair<int,int> > g[n+1];
    vector<int> dist(n+1,max);
    vector<bool> viz(n+1,false);
    dist[1]=0;
    viz[1]=true;
    int a,b,c;
    for(int i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        g[a].push_back(make_pair(b, c));
    }
    Q.push(1);
    while(!Q.empty())
    {
        int i=Q.front();
        Q.pop();
        viz[i]=false;
        for(it=g[i].begin(),eit=g[i].end();it !=eit; ++it)
            if(dist[i] + it->second < dist[it->first])
            {
                dist[it->first] = dist[i] + it->second;
                if(!viz[it->first])
                {
                    viz[it->first]=true;
                    Q.push(it->first);
                }
            }
    }
    for(int i=2;i<=n;i++)
        fout<<(dist[i]==max ? 0:dist[i])<<' ';
    return 0;
}