#include <fstream>
#include <queue>
#include <vector>
#define inf 2000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,frec[50010],i,j,a,b,c,ans[50010],lung,cost,dest;
vector< pair<int,int> > v[250010];
queue<int> coada;
pair<int,int> jeg;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i){
        fin>>a>>b>>c;
        jeg=make_pair(b,c);
        v[a].push_back(jeg);
    }

    for(i=2;i<=n;++i)
        ans[i]=inf;
    coada.push(1);
    while(!coada.empty()){
        a=coada.front();
        lung=v[a].size();
        for(i=0;i<lung;++i)
        {
            dest=v[a][i].first;
            cost=v[a][i].second;
            if(ans[dest] > ans[a] + cost){
                ans[dest]=ans[a] + cost;
                coada.push(dest);
            }
        }
        coada.pop();
    }
    for(i=2;i<=n;++i)
        fout<<ans[i] % inf<<" ";
    return 0;
}