#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int n,m,p,x,y,c;
int INF=0x3f3f3f3f;
using P =pair<int,int>;
vector<vector<P>> G;
vector<int> Minime;
vector<int> Prev;
vector<bool> fr;
struct cmp{
    bool operator () (const int &a, const int &b)
    {
        return Minime[a]>Minime[b];
    }
};
priority_queue<int,vector<int>,cmp> Q;
int main()
{
    cin>>n>>m;
    p=1;
    G.resize(n+1);
    Minime.resize(n+1);
    Prev.resize(n+1);
    fr.resize(n+1);
    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>c;
        G[x].push_back({y,c});
    }
    for(int i=1;i<=n;i++)
     Minime[i]=INF;
    Minime[p]=0;
    Q.push(p);
    while(!Q.empty())
    {
        int nod=Q.top();
        fr[nod]=1;
        Q.pop();
        ///cout<<nod<<" "<<Minime[nod]<<'\n';
        for(int j=0;j<G[nod].size();j++)
        {
            int vecin=G[nod][j].first;
            if(!fr[vecin])
            {
            int new_cost=Minime[nod]+G[nod][j].second;
            if(new_cost<Minime[vecin])
            {
                Minime[vecin]=new_cost;
                Q.push(vecin);
                Prev[vecin]=nod;
            }
            }
        }
    }
    for(int i=2;i<=n;i++)
      if(Minime[i]==INF)
        cout<<"0 ";
    else
     cout<<Minime[i]<<" ";
    cout<<'\n';
    return 0;
}