#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int i,n,m,k,start,nod,x,y,d[100009],cost;
bool inside[100000];
vector< pair<int,int> > v[100009];
queue <int> q;

void bellman()
{
    int i,j,nod;
    q.push(1);
    inside[1]=true;
    while(! q.empty())
    {
        nod=q.front();
        inside[nod]=false;
        q.pop();
        for(i=0;i<v[nod].size();i++)
        {
            if(d[v[nod][i].first] > d[nod]+v[nod][i].second)
            {
                d[v[nod][i].first] = d[nod]+v[nod][i].second;

                if(inside[v[nod][i].first]==false){
                    inside[v[nod][i].first]=true;
                    q.push(v[nod][i].first);
                }
            }
        }

    }

}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    for(i=2;i<=n;i++)
    {
        d[i]=1000000000;
        inside[i]=false;
    }
    bellman();

    for(i=2;i<=n;i++)
    {
        if(d[i]!= 1000000000)
        fout<<d[i]<<" ";
        else fout<<"0 ";
    }
}