#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m;
const int oo =(1<<31)-1;
int dist[50005];
bool inCoada[50005];
vector <pair <int , int> > noduri[50005];
class compara{
    public:
bool operator()(int x, int y){return (dist[x] > dist[y]);}

};
struct el{int i;};

priority_queue < int , vector<int>, compara > coada;


void citire(){int i,x,y,c;
    fin>>n>>m;
               for(i=0;i<m;i++){fin>>x>>y>>c;
                                 noduri[x].push_back(make_pair(y,c)); }



    }
    void dijkstra(int nodStart){for(int i=1;i<=n;i++){dist[i]=oo;}
    dist[nodStart]=0;
    coada.push(nodStart);
    inCoada[nodStart]=true;
    while(!coada.empty()){

        int actual=coada.top();
        coada.pop();
        inCoada[actual]=false;
        for(size_t i=0; i<noduri[actual].size();i++)
        { int vecin =noduri[actual][i].first;
          int cost = noduri[actual][i].second;
          if(dist[actual] + cost < dist[vecin]){
            dist[vecin]=dist[actual]+cost;
            if(inCoada[vecin]==false){inCoada[vecin]=true;coada.push(vecin);            }

          }

        }

    }



    }
int main()
{
citire();
dijkstra(1);
for(int i=2;i<=n;i++){if(dist[i]==oo){fout<<0<<" ";}
                      else{fout<<dist[i]<<" ";}

}
}